О графах, в которых окрестности вершин являются реберно регулярными графами без $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