Дистанционно регулярные графы с массивами пересечений $\{7,6,6;1,1,2\}$ и $\{42,30,2;1,10,36\}$ не существуют
А. А. Махневa,
В. В. Биткинаb,
А. К. Гутноваbc a Институт математики и механики им. Н. Н. Красовского, Россия, 620990, Екатеринбург, ул. С. Ковалевской, 16
b Северо-Осетинский государственный университет им. К. Л. Хетагурова, Россия, 362025, Владикавказ, ул. Ватутина, 44–46
c Северо-Кавказский центр математических исследований, Россия, 362025, Владикавказ, ул. Ватутина, 19
Аннотация:
Пусть
$\Gamma$ — дистанционно регулярный граф диаметра 3 без треугольников,
$u$ — вершина графа
$\Gamma$,
$\Delta^i=\Gamma_i(u)$ и
$\Sigma^i=\Delta^i_{2,3}$. Тогда
$\Sigma^i$ — регулярный граф без 3-коклик степени
$k'=k_i-a_i-1$ на
$v'=k_i$ вершинах. Заметим, что для несмежных вершин
$y,z\in \Sigma^i$ имеем $\Sigma^i=\{y,z\}\cup \Sigma^i(y)\cup \Sigma^i(z)$. Поэтому для
$\mu'=|\Sigma^i(y)\cap \Sigma^i(z)|$ имеем равенство
$v'=2k'+2-\mu'$. Отсюда граф
$\Sigma$ является кореберно регулярным с параметрами
$(v',k',\mu')$. В работе доказано, что дистанционно регулярный граф с массивом пересечений
$\{7,6,6;1,1,2\}$ не существует. В статье М. С. Нировой «On distance-regular graphs with
$\theta_2=-1$» показано, что если существует сильно регулярный граф с параметрами
$(176,49,12,14)$, в котором окрестности вершин являются
$7\times 7$-решетками, то существует и дистанционно регулярный граф с массивом пересечений
$\{7,6,6;1,1,2\}$. М. П. Голубятников заметил, что для дистанционно регулярного графа
$\Gamma$ с массивом пересечений
$\{7,6,6;1,1,2\}$ граф
$\Gamma_2$ является дистанционно регулярным с массивом пересечений
$\{42,30,2;1,10,36\}$. С помощью этого результата и вычисления тройных чисел пересечений доказано, что дистанционно регулярные графы с массивами пересечений
$\{7,6,6;1,1,2\}$ и
$\{42,30,2;1,10,36\}$ не существуют.
Ключевые слова:
дистанционно регулярный граф, граф без треугольников, тройные числа пересечений.
УДК:
519.17
MSC: 20D45 Поступила в редакцию: 14.12.2020
DOI:
10.46698/y2738-1800-0363-i