О двудольных $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