Дистанционно регулярные графы с массивами пересечений $\{104,70,25;1,7,80\}$ и $\{272,210,49;1,15,224\}$ не существуют
М. П. Голубятников Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
Аннотация:
В 2019 г. И. Н. Белоусов, А. А. Махнев и М. С. Нирова получили описание
$Q$-полиномиальных дистанционно регулярных графов
$\Gamma$ диаметра 3 с сильно регулярными графами
$\Gamma_2$ и
$\Gamma_3$, где графы
$\Gamma_2$ и
$\Gamma_3$ имеют то же множество вершин, что и граф
$\Gamma$, и в этих графах вершины смежны тогда и только тогда, когда они находятся в графе
$\Gamma$ на расстоянии
$2$ или
$3$ соответственно. Некоторые
$Q$-полиномиальные дистанционно регулярные графы
$\Gamma$ с сильно регулярными графами
$\Gamma_2$ и
$\Gamma_3$ имеют массивы пересечений
$$\Big\lbrace \frac{(s^2+su-1)(u^2-1)}{s^2-1},\frac{(u^2-s^2)su}{s^2-1},u^2;1,\frac{u^2-s^2}{s^2-1},\frac{su^3-su}{s^2-1}\Big\rbrace.$$
Для небольших значений
$s$ и
$u$ получаем массивы пересечений
$\{104,70,25;1,7,80\}$ (
$u=5$,
$s=2$) и
$\{272,210,49;1,15,224\}$ (
$u=7$,
$s=2$). В этой работе мы доказываем, что дистанционно регулярные графы с такими массивами пересечений не существуют. Также мы изучаем свойства локальных подграфов в гипотетическом дистанционно регулярном графе с массивом пересечений
$\{399, 320, 64; 1, 20, 336\}$ (
$u=8$,
$s=2$).
Ключевые слова:
дистанционно регулярный граф, $Q$-полиномиальный граф.
УДК:
519.17
MSC: 05C25 Поступила в редакцию: 13.03.2020
Исправленный вариант: 21.10.2020
Принята в печать: 26.10.2020
DOI:
10.21538/0134-4889-2020-26-4-98-105