Аннотация:
Граф Крейна без треугольников $\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$-схемы.
Ключевые слова:дистанционно регулярный граф, сильно регулярный граф.
Hainan Provincial Natural Science Foundation of China
Исследование выполнено при поддержке Естественнонаучного фонда Китая (проект № 12171126) и гранта Лаборатории инженерного моделирования и статистических вычислений провинции Хайнань.
Поступила в редакцию: 22.08.2023 Исправленный вариант: 12.09.2023 Принята в печать: 18.09.2023
Образец цитирования:
Минчжу Чэнь, А. А. Махнев, М. С. Нирова, “О графах, в которых окрестности вершин являются реберно регулярными графами без $3$-лап”, Тр. ИММ УрО РАН, 29, № 4, 2023, 279–282; Proc. Steklov Inst. Math. (Suppl.), 323, suppl. 1 (2023), S53–S55