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

Труды Института математики НАН Беларуси, 2024, том 32, номер 1, страницы 57–63 (Mi timb383)

ДИСКРЕТНАЯ МАТЕМАТИКА И МАТЕМАТИЧЕСКАЯ КИБЕРНЕТИКА

О дистанционно регулярных графах диаметра $3$ и степени $44$

М. Ченьa, А. А. Махневbc, В. С. Климинc

a Университет провинции Хайнань, г. Хэйкоу, Китай
b Институт математики и механики им. Н. Н. Красовского УрО РАН, г. Екатеринбург, Россия
c Уральский федеральный университет, г. Екатеринбург, Россия

Аннотация: Дистанционно регулярный граф $\Gamma$ диаметра $3$ с сильно регулярными графами $\Gamma_2$ и $\Gamma_3$ имеет массив пересечений $\{r(c_2+1)+a_3$, $rc_2$, $a_3+1$; 1, $c_2$, $r(c_2+1)\}$ (М. С. Нирова). Для дистанционно регулярного графа $\Gamma$ диаметра $3$ и степени $44$ имеется $7$ допустимых массивов пересечений. Для каждого из них граф $\Gamma_3$ сильно регулярен. Для массива пересечений $\{44,30,5; 1, 3,40\}$ имеем $a_3=4$, $c_2=3$, $r=10$, $\Gamma_2$ имеет параметры $(540, 440, 358, 360)$ и $\Gamma_3$ имеет параметры $(540, 55, 10, 5)$. Граф не существует (Кулен–Пак). Для массива пересечений $\{44, 35, 3; 1, 5, 42\}$ граф $\Gamma_3$ имеет параметры $(375, 22, 5, 1)$. Граф не существует (окрестность вершины – объединение изолированных $6$-клик). В работе доказано, что дистанционно регулярные графы с массивами пересечений $\{44, 36, 5; 1, 9, 40\}$, $\{44, 36, 12; 1, 3, 33\}$ и $\{44, 42, 5; 1, 7, 40\}$ не существуют.

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

УДК: 519.17

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



© МИАН, 2024