RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Института математики и механики УрО РАН // Архив

Тр. ИММ УрО РАН, 2023, том 29, номер 4, страницы 279–282 (Mi timm2054)

О графах, в которых окрестности вершин являются реберно регулярными графами без $3$-лап

Минчжу Чэньa, А. А. Махневbc, М. С. Нироваd

a Hainan University
b Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
c Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
d Кабардино-Балкарский государственный университет им. Х. М. Бербекова, г. Нальчик

Аннотация: Граф Крейна без треугольников $\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$-схемы.

Ключевые слова: дистанционно регулярный граф, сильно регулярный граф.

УДК: 519.17

MSC: 05E30, 05C50

Поступила в редакцию: 22.08.2023
Исправленный вариант: 12.09.2023
Принята в печать: 18.09.2023

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


 Англоязычная версия: Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2023, 323, suppl. 1, S53–S55

Реферативные базы данных:


© МИАН, 2024