М.П. Голубятников. Дистанционно регулярные графы с массивами пересечений {104,70,25;1,7,80} и {272,210,49;1,15,224} не существуют ...С. 98-105

УДК 519.17

MSC: 05C25

DOI: 10.21538/0134-4889-2020-26-4-98-105

Исследование выполнено за счет гранта Российского научного фонда (проект 19-71-10067).

В 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$-полиномиальный граф

СПИСОК ЛИТЕРАТУРЫ

1.   Белоусов И.Н., Махнев А.А., Нирова М.С. О дистанционно регулярных $Q$-полиномиальных графах $\Gamma$ с сильно регулярными графами $\Gamma_2$ и $\Gamma_3$ // Сиб. электрон. мат. изв. 2019. Т. 16. C. 1358–1365. doi: 10.33048/semi.2019.16.096 

2.   Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs, Berlin; Heidelberg; N Y: Springer-Verlag, 1989. 495 p.

3.   Coolsaet K., Jurishich A. Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs // J. Comb. Theory. Ser. A. 2008. Vol. 115. P. 1086–1095. doi: 10.1016/j.jcta.2007.12.001 

4.   Gavrilyuk A. L., Koolen J. H., The Terwilliger polynomial of a $Q$-polynomial distance-regular graph and its application to the pseudo-partition graphs // Linear Algebra Appl. 2015. Vol. 466. P. 117–140.

Поступила 13.03.2020

После доработки 21.10.2020

Принята к публикации 26.10.2020

Голубятников Михаил Петрович
математик
Институт математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: mike_ru1@mail.ru

Ссылка на статью: М.П. Голубятников.  Дистанционно регулярные графы с массивами пересечений {104,70,25;1,7,80} и {272,210,49;1,15,224} не существуют // Тр. Ин-та математики и механики УрО РАН. 2020. Т.26, № 4. С. 98-105

English

M.P. Golubyatnikov. Distance-regular graphs with intersection arrays {104, 70, 25; 1, 7, 80} and {272, 210, 49; 1, 15, 224} do not exist

I.N. Belousov, A.A. Makhnev, and M.S. Nirova in 2019 described $Q$-polynomial distance-regular graphs $\Gamma$ of diameter 3 with strongly regular graphs $\Gamma_2$ and $\Gamma_3$, where the graphs $\Gamma_2$ and $\Gamma_3$ have the same vertices as $\Gamma$ and these vertices are adjacent if and only if they are at distance $2$ or $3$, respectively. Some of the $Q$-polynomial distance-regular graphs $\Gamma$ with strongly regular graphs $\Gamma_2$ and $\Gamma_3$ have intersection arrays
$$\left\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}\right\rbrace.$$
For small values of $s$ and $u$,  we have intersection arrays $\{104,70,25;1,7,80\}$ ($u=5$, $s=2$) and $\{272,210,49;1,15,224\}$ ($u=7$, $s=2$). We prove that distance-regular graphs with such arrays do not exist. We also study the properties of a local subgraph in a hypothetical distance-regular graph with intersection array $\{399, 320, 64; 1, 20, 336\}$ ($u=8$, $s=2$).

Keywords: distance-regular graph, $Q$-polynomial graph

Received March 13, 2020

Revised October 21, 2020

Accepted October 26, 2020

Funding Agency: This work was supported by the Russian Science Foundation (project no. 19-71-10067).

Mikhail Petrovich Golubyatnikov, doctoral student, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: mike_ru1@mail.ru

Cite this article as: M.P. Golubyatnikov. Distance-regular graphs with intersection arrays {104,70,25;1,7,80} and {272,210,49;1,15,224} do not exist, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2020, vol. 26, no. 4, pp. 98–105.

[References -> on the "English" button bottom right]