В.В. Биткина, А.К. Гутнова. О графах Шилла с $b=6$ и $b_2\ne c_2$ ... С. 74-83

УДК 519.17

MSC: 20D05

DOI: 10.21538/0134-4889-2022-28-2-74-83

Работа выполнена при финансовой поддержке Министерства науки и высшего образования РФ, cоглашение № 075-02-2022-890.

Графом Шилла называется дистанционно регулярный граф $\Gamma$ (с валентностью $k$) диаметра $3$, имеющий второе собственное значение $\theta_1$, равное $a=a_3$. В этом случае $a$ делит $k$ и полагают $b=b(\Gamma)=k/a$. Граф Шилла имеет массив пересечений $\{ab,(a+1)(b-1),b_2;1,c_2,a(b-1)\}$. Дж. Кулен и Ж. Пак показали, что для заданного числа $b$ существует только конечное число графов Шилла. Допустимые массивы пересечений графов Шилла для  $b\in \{2,3\}$ найдены в статье Дж. Кулена, Ж. Пака. В статье А.А. Махнева, И.Н. Белоусова найдены допустимые массивы пересечений графов Шилла для  $b\in \{4,5\}$. Там же доказано, что $Q$-полиномиальные графы Шилла с $b=5$ не существуют, а также найдены $Q$-полиномиальные графы Шилла с $b=6$. $Q$-полиномиальный граф Шилла с $b=6$ имеет массив пересечений $\{42t,5(7t+1),3(t+3);1,3(t+3),35t\}$, где  $t\in \{7,12,17,27,57\}$, $\{372,315,75;1,15,310\}$, $\{744,625,125;1,25,620\}$, $\{930,780,150;1,30,775\}$, $\{312,265,48;1,24,260\}$, $\{624,525,80;1,40,520\}$, $\{1794,1500,200;1,100,1495\}$ или $\{5694,4750,600;1,300,4745\}$. Ранее было доказано, что графы с массивами пересечений $\{372,315,75;1,15,310\}$, $\{744,625,125;1,25,620\}$, $\{1794,1500,200;1,100,1495\}$ и $\{42t,5(7t+1),3(t+3);1,3(t+3),35t\}$ не существуют. В работе доказано, что дистанционно регулярные графы с массивами пересечений $\{312,265,48;1,24,260\}$, $\{624,525,80;1,40,520\}$ и $\{930,780,150;1,30,775\}$ не существуют.

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

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

1.   Brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs. Berlin; Heidelberg; NY: Springer-Verlag, 1989. 495 p. ISBN: 0387506195 .

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

3.   Belousov I. N., Makhnev A. A. Shilla graphs with b = 5 and b = 6 // Ural Math. J. 2021. Vol. 7, no. 2. P. 51–58. doi: 10.15826/umj.2021.2.004 

4.   Jurishich A., Vidali J. Extremal 1-codes in distance-regular graphs of diameter 3 // Des. Codes Cryptogr. 2012. Vol. 65. P. 29–47.

5.   Gavrilyuk A. L., Koolen J. H. A characterization of the graphs of bilinear $(d×d)$-forms over $\mathbb {F}_2$ // Combinatorika. 2010. Vol. 39. P. 289–321.

Поступила 17.02.2022

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

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

Биткина Виктория Васильевна
канд. физ.-мат. наук
доцент кафедры прикладной математики и информатики
Северо-Осетинский государственный университет им. К.Л. Хетагурова
г. Владикавказ
e-mail: bviktoriyav@mail.ru

Гутнова Алина Казбековна
канд. физ.-мат. наук
доцент кафедры прикладной математики и информатики
Северо-Осетинский государственный университет им. К.Л. Хетагурова
г. Владикавказ
e-mail: gutnovaalina@gmail.com

Ссылка на статью: В.В. Биткина, А.К. Гутнова. О графах Шилла с $b=6$ и $b_2\ne c_2$ // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 2. С. 74-83

English

V.V. Bitkina, A.K. Gutnova. On Shilla graphs with $b=6$ and $b_2\ne c_2$

A Shilla graph is a distance-regular graph $\Gamma$ (with valency $k$) of diameter $3$ that has second eigenvalue $\theta_1$ equal to $a=a_3$. In this case $a$ divides $k$ and the parameter $b=b(\Gamma)=k/a$ is defined. 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 fixed $b$ there are finitely many Shilla graphs. Admissible intersection arrays of Shilla graphs were found for $b\in \{2,3\}$ by Koolen and Park in 2010 and for $b\in \{4,5\}$ by A.A. Makhnev and I.N. Belousov in 2021. Makhnev and Belousov also proved the nonexistence of $Q$-polynomial Shilla graphs with $b=5$ and found $Q$-polynomial Shilla graphs with $b=6$. A $Q$\nobreakdash-polynomial Shilla graph with $b=6$ has intersection array $\{42t,5(7t+1),3(t+3);$ $1,3(t+3),35t\}$ with $t\in \{7,12,17,27,57\}$, $\{372,315,75;1,15,310\}$, $\{744,625,125;1,25,620\}$, $\{930,780,150;1,30,775\}$, $\{312,265,48;1,24,260\}$, $\{624,525,80;1,40,520\}$, $\{1794,1500,200;1,100,1495\}$, or $\{5694,4750,600;1,300,4745\}$. The nonexistence of graphs with intersection arrays $\{372,315,75;1,15,310\}$, $\{744,625,$ $125;1,25,620\}$, $\{1794,1500,200;1,100,1495\}$, and $\{42t,5(7t+1),3(t+3);1,3(t+3),35t\}$ was proved earlier. We prove that distance-regular graphs with intersection arrays $\{312,265,48;1,24,260\}$, $\{624,525,80;1,40,520\}$, and $\{930,780,150;1,30,775\}$ do not exist.

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

Received February 17, 2022

Revised April 28, 2022

Accepted April 30, 2022

Funding Agency: This study supported by the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-02-2022-890).

Viktoriya V. Bitkina, Cand. Phys.-Math. Sci., North Ossetian State University, Vladikavkaz, 362025 Russia, e-mail: bviktoriyav@mail.ru

Alina K. Gutnova, Cand. Phys.-Math. Sci., North Ossetian State University, Vladikavkaz, 362025 Russia, e-mail: gutnovaalina@gmail.com

Cite this article as: V.V. Bitkina, A.K. Gutnova. On Shilla graphs with $b=6$ and $b_2\ne c_2$, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 2, pp. 74–83.

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