On the strong regularity of some edge-regular graphs

A. A. Makhnev

Izvestiya. Mathematics , Tome 68 (2004) no. 1, pp. 159-180

Résumé

An undirected graph is said to be edge-regular with parameters $(v,k,\lambda)$ if it has $v$ vertices, each vertex has degree $k$, and each edge belongs to $\lambda$ triangles. We put $b_1=v-k-\lambda$. Brouwer, Cohen, and Neumaier proved that every connected edge-regular graph with $\lambda\geqslant k+1/2-\sqrt{2k+2}$ (equivalently, with $k\geqslant b_1(b_1+3)/2+1$) is strongly regular. In this paper we construct an example of an edge-regular, not strongly regular graph on 36 vertices with $k=27=b_1(b_1+3)/2$. This shows that the estimate above is sharp. We prove that every connected edge-regular graph with $\lambda\geqslant k+1/2-\sqrt{2k+8}$ (equivalently, $k\geqslant b_1(b_1+3)/2-2$ either satisfies $b_1\leqslant 3$, or has parameters $(36,27,20)$ or $(64,52,42)$, or is strongly regular.