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=\underset{uv\in E}{max}|N(u)\cup N(v)|$, then $4m\le 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$.