Geodesic
On the strong regularity of some edge-regular graphs
Izvestiya. Mathematics , Tome 68 (2004) no. 1, pp. 159-180.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{IM2_2004_68_1_a5,
     author = {A. A. Makhnev},
     title = {On the strong regularity of some edge-regular graphs},
     journal = {Izvestiya. Mathematics },
     pages = {159--180},
     publisher = {mathdoc},
     volume = {68},
     number = {1},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2004_68_1_a5/}
}
TY  - JOUR
AU  - A. A. Makhnev
TI  - On the strong regularity of some edge-regular graphs
JO  - Izvestiya. Mathematics 
PY  - 2004
SP  - 159
EP  - 180
VL  - 68
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2004_68_1_a5/
LA  - en
ID  - IM2_2004_68_1_a5
ER  - 
%0 Journal Article
%A A. A. Makhnev
%T On the strong regularity of some edge-regular graphs
%J Izvestiya. Mathematics 
%D 2004
%P 159-180
%V 68
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2004_68_1_a5/
%G en
%F IM2_2004_68_1_a5
A. A. Makhnev. On the strong regularity of some edge-regular graphs. Izvestiya. Mathematics , Tome 68 (2004) no. 1, pp. 159-180. http://geodesic.mathdoc.fr/item/IM2_2004_68_1_a5/

[1] Brouwer A. E., Cohen A. M., Neumaier A., Distance-regular graphs, Springer-Verlag, Berlin, 1989 | MR

[2] Erickson M., Fernando S., Haemers W., Hardy D., Hemmeter J., “Deza graphs: a generalization of strongly regular graphs”, J. Comb. Designs, 7 (1999), 395–405 | 3.0.CO;2-U class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[3] Makhnev A. A., Minakova I. M., “Ob odnom klasse reberno regulyarnykh grafov”, Izv. Gomelskogo gos. un-ta. Voprosy algebry, 3 (16) (2000), 145–154

[4] Makhnev A. A., Vedenev A. A., Kuznetsov A. N., Nosov V. V., “O khoroshikh parakh v reberno regulyarnykh grafakh”, Diskret. matem., 15 (2003), 77–97 | MR | Zbl

[5] Makhnev A. A., “O rasshireniyakh chastichnykh geometrii, soderzhaschikh malye $\mu$-podgrafy”, Diskr. analiz i issled. operatsii, 3:3 (1996), 71–83 | MR | Zbl