УДК 519.17
MSC: 20D05
DOI: 10.21538/0134-4889-2022-28-2-74-83
Полный текст статьи (Full text)
Работа выполнена при финансовой поддержке Министерства науки и высшего образования РФ, 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]