RUS  ENG
Полная версия
ЖУРНАЛЫ // Владикавказский математический журнал // Архив

Владикавк. матем. журн., 2025, том 27, номер 3, страницы 21–27 (Mi vmj964)

О двудольных $Q$-полиномиальных графах диаметра, не большего $5$

В. В. Биткинаa, А. А. Махневbc

a Северо-Осетинский государственный университет им. К. Л. Хетагурова, Россия, 362025, Владикавказ, ул. Ватутина, 44–46
b Хайнаньский университет, Китай, 570228, Хэйкоу, Хайнань, пр. Ренмин, 58
c Институт математики и механики им. Н. Н. Красовского, Россия, 620990, Екатеринбург, ул. С. Ковалевской, 16

Аннотация: Пусть $u$ — вершина двудольного $Q$-полиномиального дистанционно регулярного графа $\Gamma$ диаметра $D\ge 3$, $\Sigma=\Gamma_D(u)$ и $\Lambda=\Sigma_2$. Тогда $\Lambda$ — дистанционно регулярный $Q$-полиномиальный граф. В случаях $D=4$ и $D=5$ граф $\Lambda$ является сильно регулярным $Q$-полиномиальным. Половинный граф $\Gamma_2$ сильно регулярен и $\Lambda$ — окрестность вершины в дополнении к $\Gamma_2$. Поэтому необходимое условие $Q$-полиномиальности $\Gamma$ — это сильная регулярность окрестностей и антиокрестностей вершин в $\Lambda$. Двудольный дистанционно регулярный граф $\Gamma$ диаметра $D\in \{4,5\}$ назовем почти $Q$-полиномиальным, если окрестности и антиокрестности вершин в дополнении его половинного графа сильно регулярны. Имеется два допустимых массива пересечений $Q$-полиномиальных графов: $\{10,9,8,7,6;1,2,3,4,10\}$ (свернутый $10$-куб) и $\{55,54,50,35,10;1,5,20,45,55\}$. Эти графы имеют сильно регулярные графы $\Lambda$ (параметры $(126,25,8,4)$ и $(210,99,48,45)$) и окрестности вершин в $\Lambda$ (параметры $(25,8,4,2)$ и $(99,48,22,24)$). Имеются два допустимых массива пересечений, отвечающих графам на $704$ вершинах: $\{26,25,24,2,1;1,2,24,25,26\}$ и $\{36,34,32,4,1;1,4,32,34,36\}$. В работе изучаются почти $Q$-полиномиальные графы диаметра $5$. Доказано, что дистанционно регулярные графы с массивами пересечений $\{26,25,24,2,1;1,2,24,25,26\}$ и $\{36,35,32,4,1;1,4,32,35,36\}$ не существуют.

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

УДК: 519.17

MSC: 05E30, 05C50

Поступила в редакцию: 23.02.2025

DOI: 10.46698/y5679-0662-9249-a



© МИАН, 2025