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
Voir la notice de l'article provenant de la source Math-Net.Ru
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},
publisher = {mathdoc},
volume = {29},
number = {4},
year = {2023},
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 PB - mathdoc 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 %I mathdoc %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/