Том 28, номер 3, 2021 г., Стр. 38-48

УДК 519.17
Махнев А. А., Голубятников М. П.
О несуществовании дистанционно регулярного графа с массивом пересечений
{53, 40, 28, 16; 1, 4, 10, 28}

Аннотация:
Рассматриваются $Q$-полиномиальные графы диаметра 4. Кроме бесконечной серии массивов пересечений {$m(2m + 1)$, $(m - 1)(2m + 1)$, $m^2$, $m$; 1, $m$, $m - 1, m(2m + 1)$} известны следующие допустимые массивы пересечений $Q$-полиномиальных графов диаметра 4 с не более чем 4096 вершинами: {5, 4, 4, 3; 1, 1, 2, 2} (нечётный граф на 9 вершинах), {9, 8, 7, 6; 1, 2, 3, 4} (свёрнутый 9-куб), {36, 21, 10, 3; 1, 6, 15, 28} (половинный 9-куб) и {53, 40, 28, 16; 1, 4, 10, 28}. В работе доказано, что дистанционно регулярного графа с массивом пересечений {53, 40, 28, 16; 1, 4, 10, 28} не существует.
Библиогр. 5.

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

DOI: 10.33048/daio.2021.28.709

Махнев Александр Алексеевич ¹
Голубятников Михаил Петрович ¹
1. Институт математики и механики им. Н. Н. Красовского,
ул. Софьи Ковалевской, 16, 620108 Екатеринбург, Россия
е-mail: makhnev@imm.uran.ru, mike_ru1@mail.ru

Статья поступила 31 марта 2021 г.
После доработки — 6 мая 2021 г.
Принята к публикации 7 мая 2021 г.

Литература

[1] Brouwer A. E., Cohen A. M., Neumaier A. Distance-regular graphs. Heidelberg: Springer, 1989.

[2] Cameron P. Permutation groups. Cambridge: Camb. Univ. Press, 1999. 220 p. (Lond. Math. Soc. Student Texts; Vol. 45).

[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.

[4] Gavrilyuk A. L., Koolen J. H. A characterization of the graphs of bilinear $d \times d$-forms over $F_2$ // Combinatorica. 2010. Vol. 39. P. 289–321.

[5] 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.