И.Н. Белоусов. Дистанционно регулярные графы Шилла с $b_2 = sc_2$ ... С. 16-26

УДК 519.17

MSC: 05C25

DOI: 10.21538/0134-4889-2018-24-3-16-26

Работа выполнена при финансовой поддержке гранта РНФ, проект 14-11-00061-П

Графом Шилла называется дистанционно регулярный граф Γ диаметра 3, имеющий второе собственное значение, равное $a = a_3$. Граф Шилла имеет массив пересечений ${ab, (a+1)(b-1),b_2; 1,c_2,a(b- 1)}$. Дж. Кулен и Ж. Пак показали, что для заданного числа b существует только конечное число графов Шилла. Там же они нашли всевозможные допустимые массивы пересечений графов Шилла для $b ∈{2, 3}$. Ранее автором совместно с А. А. Махневым изучены графы Шилла с $b_2 = c_2$. В данной работе исследуются графы Шилла с $b_2 = sc_2$; здесь $s$ — целое число, большее 1. Для графов Шилла с указанным условием и вторым неглавным собственным значением -1 найдены пять бесконечных серий допустимых массивов пересечений. Показано, что в случае графов Шилла без треугольников с условием $b_2 = sc_2$ и $b < 170$ возможны лишь 6 допустимых массивов пересечений. В случае Q-полиномиального графа Шилла с условием $b_2 = sc_2$ найдены допустимые массивы пересечений в случаях $b = 4$ и $b = 5$. На основании этого результата удалось получить список допустимых массивов пересечений графов Шилла для $b ∈{4, 5}$ в общем случае.

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

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

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

2.   Koolen J.H., Park J. Shilla distance-regular graphs // Europ. J. Comb. 2010. Vol. 31, no. 8. P. 2064–2073. doi: 10.1016/j.ejc.2010.05.012 .

3.   Махнев A. A., Нирова M. С. Дистанционно регулярные графы Шилла с $b_2 = c_2$ // Мат. заметки. 2018. Т. 103, вып. 5. С.  730–744. doi: 10.4213/mzm11503 .

4.   Махнев А. А., Белоусов И. Н. К теории графов Шилла $b_2 = c_2$ // Сиб. электрон. мат. изв. 2017. Vol. 14. P. 1135–1146. doi: 10.17377/semi.2017.14.097 .

5.   Coolsaet K. Distance-regular graph with intersection array {21,16,8;1,4,14} does not exist // Europ. J. Comb. 2005. Vol. 26, no. 5. P. 709–716. doi: 10.1016/j.ejc.2004.04.005 .

Поступила 20.02.2018

Белоусов Иван Николаевич
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет,
г. Екатеринбург
e-mail: i_belousov@mail.ru

English

I. N. Belousov. Shilla distance-regular graphs with $b_2 = sc_2$.

A Shilla graph is a distance-regular graph $\Gamma$ of diameter 3 whose second eigenvalue is $a=a_3$. A Shilla graph has intersection array $\{ab,(a+1)(b-1),b_2;1,c_2,a(b-1)\}$. J. Koolen and J. Park showed that, for a given number $b$, there exist only finitely many Shilla graphs. They also found all possible admissible intersection arrays of Shilla graphs for $b\in \{2,3\}$. Earlier the author together with A.A. Makhnev studied Shilla graphs with $b_2=c_2$. In the present paper, Shilla graphs with $b_2=sc_2$, where $s$ is an integer greater than $1$, are studied. For Shilla graphs satisfying this condition and such that their second nonprincipal eigenvalue is $-1$, five infinite series of admissible intersection arrays are found. It is shown that, in the case of Shilla graphs without triangles in which $b_2=sc_2$ and $b<170$, only six admissible intersection arrays are possible. For a $Q$-polynomial Shilla graph with $b_2=sc_2$, admissible intersection arrays are found in the cases $b=4$ and $b=5$, and this result is used to obtain a list of admissible intersection arrays of Shilla graphs for $b\in\{4,5\}$ in the general case.
 

Keywords: distance-regular graph, graph automorphism.

The paper was received by the Editorial Office on June 26, 2018.

Funding Agency: This work was supported by the Russian Science Foundation (project no. 14-11-00061-П).

Ivan Nikolaevich Belousov, Cand. Sci. (Phis.-Math.), Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: i_belousov@mail.ru.

 

 

 

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