Минчжу Чень, А. А. Махнев, М. С. Нирова. О графах, в которых окрестности вершин являются реберно регулярными графами без 3-лап ... С. 279-282

УДК 519.17

MSC: 05E30, 05C50

DOI: 10.21538/0134-4889-2023-29-4-279-282

Исследование выполнено при поддержке Естественнонаучного фонда Китая (проект № 12171126) и гранта Лаборатории инженерного моделирования и статистических вычислений провинции Хайнань.

Полный текст статьи (Full text)

Статья переведена: ISSN 0081-5438 

Proceedings of the Steklov Institute of Mathematics, 2023, Vol. 323, Suppl. 1, pp. S53–S55. (Abstract)

Граф Крейна без треугольников $\mathrm{Kre}(r)$ является сильно регулярным с параметрами $((r^2+3r)^2,r^3+3r^2+r,0,r^2+r)$. Известно существование таких графов только для $r=1$ (дополнительный граф для графа Клебша) и $r=2$ (граф Хигмена — Симса). А.Л. Гаврилюк и А.А. Махнев доказали, что граф $\mathrm{Kre}(3)$ не существует. Позднее А.А. Махнев доказал, что граф $\mathrm{Kre}(4)$ не существует. Граф $\mathrm{Kre}(r)$ — это единственный сильно регулярный граф без треугольников, в котором антиокрестность вершины $\mathrm{Kre}(r)'$ сильно регулярна. Граф $\mathrm{Kre}(r)'$ имеет параметры $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$. В работе уточняется один результат А.А. Махнева  о графах, в которых окрестности вершин являются сильно регулярными графами без $3$-коклик. Как следствие доказано, что граф $\mathrm{Kre}(r)$ существует тогда и только тогда, когда граф $\mathrm{Kre}(r)'$ существует и является дополнительным графом к блочному графу квазисимметричной $2$-схемы.
      
Ключевые слова: дистанционно регулярный граф, сильно регулярный граф

СПИСОК ЛИТЕРАТУРЫ

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

2.   Гаврилюк А.Л., Махнев А.А. Крейн графы без треугольников // Докл. АН. 2005. Т. 403, № 6. C. 727–730.

3.   Махнев А. Граф $\mathrm{Kre}(4)$ не существует // Докл. АН. 2017. Vol. 475, № 3. P. 251–253. doi: 10.7868/S0869565217210022

4.   Махнев А.А. Об одном классе графов без 3-лап // Мат. заметки. 1998. Т. 63, № 3. С. 407–413.

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

Поступила 22.08.2023

После доработки 12.09.2023

Принята к публикации 18.09.2023

Минчжу Чень
Хайнаньский университет, г. Хэйкоу, Китай
e-mail: 994194@hainanu.edu.cn

Махнев Александр Алексеевич
д-р физ.-мат. наук, чл.-корр. РАН
главный науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
Уральский федеральный университет
г. Екатеринбург
e-mail: makhnev@imm.uran.ru

Нирова Марина Сефовна
канд. физ.-мат. наук, доцент
Кабардино-Балкарский госуниверситет
г. Нальчик
e-mail: nirova_m@mail.ru

Ссылка на статью: Минчжу Чень, А. А. Махнев, М. С. Нирова. О графах, в которых окрестности вершин являются реберно регулярными графами без 3-лап // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 4. С. 279-282

English

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

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

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.

[References -> on the "English" button bottom right]