Geodesic
On Graphs in Which the Neighborhoods of Vertices Are Edge-Regular Graphs without 3-Claws
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 4, pp. 279-282 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The triangle-free Krein graph Kre$(r)$ is strongly regular with parameters $((r^2+3r)^2,$ $r^3+3r^2+r,0,r^2+r)$. The existence of such graphs is known only for $r=1$ (the complement of the Clebsch graph) and $r=2$ (the Higman–Sims graph). A. L. Gavrilyuk and A. A. Makhnev proved that the graph Kre$(3)$ does not exist. Later Makhnev proved that the graph Kre$(4)$ does not exist. The graph Kre$(r)$ is the only strongly regular triangle-free graph in which the antineighborhood of a vertex Kre$(r)'$ is strongly regular. The graph Kre$(r)'$ has parameters $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$. This work clarifies Makhnev's result on graphs in which the neighborhoods of vertices are strongly regular graphs without $3$-cocliques. As a consequence, it is proved that the graph Kre$(r)$ exists if and only if the graph Kre$(r)'$ exists and is the complement of the block graph of a quasi-symmetric $2$-design.
Keywords: distance-regular graph, strongly regular graph. 
@article{TIMM_2023_29_4_a22,
     author = {M. Chen and A. A. Makhnev and M. S. Nirova},
     title = {On {Graphs} in {Which} the {Neighborhoods} of {Vertices} {Are} {Edge-Regular} {Graphs} without {3-Claws}},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {279--282},
     year = {2023},
     volume = {29},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2023_29_4_a22/}
}
TY  - JOUR
AU  - M. Chen
AU  - A. A. Makhnev
AU  - M. S. Nirova
TI  - On Graphs in Which the Neighborhoods of Vertices Are Edge-Regular Graphs without 3-Claws
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2023
SP  - 279
EP  - 282
VL  - 29
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/TIMM_2023_29_4_a22/
LA  - ru
ID  - TIMM_2023_29_4_a22
ER  - 
%0 Journal Article
%A M. Chen
%A A. A. Makhnev
%A M. S. Nirova
%T On Graphs in Which the Neighborhoods of Vertices Are Edge-Regular Graphs without 3-Claws
%J Trudy Instituta matematiki i mehaniki
%D 2023
%P 279-282
%V 29
%N 4
%U http://geodesic.mathdoc.fr/item/TIMM_2023_29_4_a22/
%G ru
%F TIMM_2023_29_4_a22
M. Chen; A. A. Makhnev; M. S. Nirova. On Graphs in Which the Neighborhoods of Vertices Are Edge-Regular Graphs without 3-Claws. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 4, pp. 279-282. http://geodesic.mathdoc.fr/item/TIMM_2023_29_4_a22/

[1] Brouwer A.E., Cohen A.M., Neumaier A., Distance-regular graphs, Springer-Verlag, Berlin; Heidelberg; NY, 1989, 495 pp. | MR | Zbl

[2] Gavrilyuk A.L., Makhnev A.A., “Krein grafy bez treugolnikov”, Dokl. AN., 403:6 (2005), 727–730 | MR | Zbl

[3] Makhnev A., “Graf $\mathrm{Kre}(4)$ ne suschestvuet”, Dokl. AN, 475:3 (2017), 251–253 | DOI | Zbl

[4] Makhnev A.A., “Ob odnom klasse grafov bez 3-lap”, Mat. zametki, 63:3 (1998), 407–413 | DOI | MR | Zbl

[5] Cameron P., van Lint J., Graphs, codes and designs, London Math. Soc. Lecture Notes Series, 43, Cambridge Univ. Press, Cambridge, 1980 | DOI | MR | Zbl