An invariant for minimum triangle-free graphs

2016/08/26 by Krüger, Oliver
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1608.07489

Abstract

We study the number of edges, e(G), in triangle-free graphs with a prescribed number of vertices, n(G), independence number, α(G), and number of cycles of length four, N(C₄;G). We in particular show that 3e(G) - 17n(G) + 35α(G) + N(C₄;G) ≥ 0 for all triangle-free graphs G. We also characterise the graphs that satisfy this inequality with equality.

Related

• Edge number critical triangle free graphs with low independence numbers
• Triangle-free planar graphs with small independence number
• On the isolation number of graphs with minimum degree four
• The independence ratio of 4-cycle-free planar graphs
• Triangle-free graphs with the maximum number of cycles