Triangle-Free Regular Graphs as an Extremal Family

Abstract

It has been shown that if \(G = (V, E)\) is a simple graph with \(n\) vertices, \(m\) edges, an average (per edge) of \(t\) triangles occurring on the edges, and \(J = \max_{uv \in E} |N(u) \cup N(v)|\), then \(4m \leq n(J+t)\). The extremal graphs for this inequality for \(J = n\) and \(J = n – 1\) have been determined. For \(J = n\), the extremal graphs are the Turán graphs with parts of equal size; notice that these are the complements of the strongly regular graphs with \(\mu = 0\). For \(J = n-1\), the extremal graphs are the complements of the strongly regular graphs with \(\mu = 1\). (The only such graphs known to exist are the Moore graphs of diameter \(2\)).

For \(J = n-2\) and \(t = 0\), it has recently been shown that the only extremal graph (except when \(n = 8, 10\)) is \(K_{n/2,n/2} – (1\text{-factor})\). Here, we use a well-known theorem of Andrásfai, Erdős, and Sós to characterize the extremal graphs for \(t = 0\), any given value of \(n-J\), and \(n\) sufficiently large (they are the regular bipartite graphs). Then we give some examples of extremal non-bipartite graphs for smaller values of \(n\).