On the strong regularity of some edge-regular graphs

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 Neuinaier proved that every connected edge-regular graph with lambda greater than or equal to k + 1/2 - root2k+ 2 (equivalently, with k greater than or equal to b(1) (b(1) + 3)/2 + 1) is strongly regular. In this paper we construct an exarnple 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 greater than or equal to k + 1/2 - root2k+ 8 (equivalently, k greater than or equal to b(1) (b(1) + 3)/2 - 2) either satisfies b(1) less than or equal to 3, or has parameters (36, 27, 20) or (64, 52, 42), or is strongly regular.