M. Chen, A.A. Makhnev, M.S. Nirova. On graphs in which the neighborhoods of vertices are edge-regular graphs without 3-claws ... P. 279-282

The triangle-free Krein graph $\mathrm{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 $\mathrm{Kre}(3)$ does not exist. Later Makhnev proved that the graph $\mathrm{Kre}(4)$ does not exist. The graph $\mathrm{Kre}(r)$ is the only strongly regular triangle-free graph in which the antineighborhood of a vertex $\mathrm{Kre}(r)'$ is strongly regular. The graph $\mathrm{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 $\mathrm{Kre}(r)$ exists if and only if the graph $\mathrm{Kre}(r)'$ exists and is the complement of the block graph of the quasi-symmetric $2$-design.

Keywords: distance-regular graph, strongly regular graph

Received August 22, 2023

Revised September 12, 2023

Accepted September 18, 2023

Funding Agency: This work was supported by the National Natural Science Foundation of China (project no. 12171126) and by a grant from the Engineering Modeling and Statistical Computing Laboratory of the Hainan Province.

Mingzhu Chen, Hainan University, Haikou, China, e-mail: 994194@hainanu.edu.cn

Aleksandr Alekseevich Makhnev, Dr. Phys.-Math. Sci., Corresponding Member RAS, Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620108 Russia, e-mail: makhnev@imm.uran.ru

Marina Sefovna Nirova, Cand. Sci. (Phys.-Math.), Kabardino-Balkarian State University named after H.M.Berbekov, Nal’chik, 360004 Russia, e-mail: nirova_m@mail.ru

REFERENCES

1.   Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; NY: Springer-Verlag, 1989. 495 p.

2.   Gavrilyuk A.L., Makhnev A.A. On Krein graphs without triangles. Dokl. Math., 2005, vol. 72, no. 1, pp. 591–594.

3.   Makhnev A. Krein graph $\mathrm{Kre}(4)$ does not exist. Dokl. Math., 2017, vol. 96, no. 1, pp. 348–350. doi: 10.1134/S1064562417040123

4.   Makhnev A.A. On some class graphs without 3-claws. Math. Notes, 1998, vol. 63, no. 3-4, pp. 357–362. doi: 10.1007/BF02317782

5.   Cameron P., van Lint J. Graphs, codes and designs. London Math. Soc. Lecture Notes Series, vol. 43, Cambridge: Cambridge Univ. Press, 1980. doi: 10.1017/CBO9780511662140

Cite this article as: 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 Mekhaniki UrO RAN, 2023, vol. 29, no. 4, pp. 279–282; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2023, Vol. 323, Suppl. 1, pp. S53–S55.