УДК 519.1
MSC: 05E30, 05C50
DOI: 10.21538/0134-4889-2022-28-2-176-186
Полный текст статьи (Full text)
Исследование выполнено за счет гранта Российского научного фонда (проект № 19-71-10067).
Рассматриваются графы Шилла, введенные Дж. Куленом и Ч. Паком. Для определения допустимых массивов пересечений графов Шилла с фиксированным параметром $b$ важную роль играют $Q$-полиномиальные графы. Для таких графов наименьшее собственное значение является минимально возможным для третьего неглавного собственного значения. В 2010 году Дж. Куленом и Ч. Паком были найдены массивы пересечений $Q$-полиномиальных графов с $b=3$ и позднее (2018) И.Н. Белоусовым с $b\in\{4,5\}$. В частности, известно, что $Q$-полиномиальный граф Шилла с $b=4$ имеет массив пересечений $\{104,81,27;1,9,78\}$, $\{156,120,36;1, 12,117\}$ или $\{20(q-2),3(5q-9),2q;1,2q,15(q-2)\}$, $q=6,9,18$. В работе доказано, что дистанционно регулярные графы с массивами пересечений $\{80,63,12;1,12,60\}$, $\{140,108,18;1,18,105\}$ и $\{320,243,36;1,36,240\}$ не существуют.
Ключевые слова: граф Шилла, дистанционно регулярный граф, $Q$-полиномиальный граф
СПИСОК ЛИТЕРАТУРЫ
1. 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
2. Jurishic A., Vidali J. Extremal 1-codes in distance-regular graphs of diameter 3 // Des. Codes Cryptogr. 2012. Vol. 65. P. 29–47.
3. Белоусов И.Н. Дистанционно регулярные графы Шилла с $b_2 = sc_2$ // Тр. Ин-та математики и механики УрО РАН. 2018. Т. 24, № 3. С. 16–26. doi: 10.21538/0134-4889-2018-24-3-16-26
4. Brouwer A.E., Sumaloj S., Worawannotai C. The nonexistence of distance-regular graphs with intersection arrays {27,20,10;1,2,18} and {36,28,4;1,2,24} // Australasian J. Comb. 2016. Vol. 66, no. 2. P. 330–332.
5. Gavrilyuk A.L., Makhnev A.A. Distance-regular graphs with intersection arrays {52,35,16; 1,4,28} and {69,48,24;1,4,46} do not exist // Des. Codes Cryptogr. 2012. Vol. 65. P. 49–54.
6. Белоусов И.Н., Махнев A.A. Дистанционно регулярный граф с массивом пересечений {105,72,24;1,12,70} не существует // Сиб. электрон. мат. изв. 2019. Т. 16. С. 206–216. doi: 10.33048/semi.2019.16.012
7. Белоусов И.Н., Махнев A.A. Дистанционно регулярные графы с массивами пересечений {42,30,12;1,6,28} и {60,45,8;1,12,50} не существуют // Сиб. электрон. мат. изв. 2018. T. 15. C. 1506–1512. doi: 10.33048/semi.2018.15.125
8. Bannai E., Ito T. Algebraic combinatorics I: Association schemes. Menlo Park: Benjamin/Cummings, 1984. 425 p. ISBN: 0805304908 .
9. Penttila T., Williford J. New families of Q-polynomial association schemes // J. Comb. Theory. Series A. 2011. Vol. 118, iss. 2. P. 502–509. doi: 10.1016/j.jcta.2010.08.001
10. Kurihara H., Nozaki H. A characterization of Q-polynomial association schemes // J. Comb. Theory. Series A. 2012. Vol. 119. P. 57–62. doi: 10.1016/j.jcta.2011.07.008
11. Suda S. On Q-polynomial association schemes of small class // Electron. J. Comb. 2012. Vol. 19, no. 1. Art. no. P68. doi: 10.37236/2157
12. Brouwer A. E., Cohen A. M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; NY: Springer-Verlag, 1989. 495 p. ISBN: 0387506195 .
13. Vidali J. Kode v razdaljno regularnih grafih: Doctorska dissertacija / Univerza v Ljubljani. Ljubljana, 2013. 155 str.
14. Coolsaet K. A distance regular graph with intersection array (21,16,8;1,4,14) does not exist // Europ. J. Comb. 2005. Vol. 26, no. 5. С. 709–716. doi: 10.1016/j.ejc.2004.04.005
15. Махнев A.A., Белоусов И.Н., Голубятников М.П., Нирова М.С. Три бесконечные серии графов Шилла не существуют // Докл. АН. Vol. 498, no. 1. 2021. C. 45–50. doi: 10.31857/S2686954321030115
Поступила 15.03.2022
После доработки 15.04.2022
Принята к публикации 18.04.2022
Махнев Александр Алексеевич
д-р физ.-мат. наук
чл.-корр. РАН, профессор
главный науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН
г. Екатеринбург
e-mail: iai@imm.uran.ru
Белоусов Иван Николаевич
канд. физ.-мат. наук
зав. отделом
Институт математики и механики им. Н.Н.Красовского УрО РАН
г. Екатеринбург
e-mail: i_belousov@mail.ru
Голубятников Михаил Петрович
Институт математики и механики им. Н.Н.Красовского УрО РАН
г. Екатеринбург
e-mail: mike_ru1@mail.ru
Ссылка на статью: А.А. Махнев, И.Н. Белоусов, М.П. Голубятников. О $Q$-полиномиальных графах Шилла c $b=4$ // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 2. С. 176-186
English
A.A. Makhnev, I.N. Belousov, M.P. Golubyatnikov. On Q-polynomial Shilla graphs with b = 4
Shilla graphs introduced by J.H. Koolen and J. Park are considered. In the problem of finding feasible intersection arrays of Shilla graphs with a fixed parameter $b$, $Q$-polynomial graphs play an important role. For such graphs, the smallest eigenvalue is the minimum possible for the third nonprincipal eigenvalue. Intersection arrays of $Q$-polynomial graphs were found for $b=3$ in 2010 by Koolen and Park and for $b\in\{4,5\}$ in 2018 by Belousov. In particular, it is known that a $Q$-polynomial Shilla graph with $b=4$ has intersection array $\{104,81,27;1,9,78\}$, $\{156,120,36;1,12,117\}$, or $\{20(q-2),3(5q-9),2q;1,2q,15(q-2)\}$, where $q=6,9,18$. We prove that distance-regular graphs with intersection arrays $\{80,63,12;1,12,60\}$, $\{140,108,18;1,18,105\}$, and $\{320,243,36;1,36,240\}$ do not exist.
Keywords: Shilla graph, distance-regular graphs, $Q$-polynomial graph
Received March 15, 2022
Revised April 15, 2022
Accepted April 18, 2022
Funding Agency: This work was supported by the Russian Science Foundation (project 19-71-10067).
Aleksandr Alekseevich Makhnev, Dr. Phys.-Math, RAS Corresponding Member, Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: makhnev@imm.uran.ru
Ivan Nikolaevich Belousov, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: i_belousov@mail.ru
Mikhail Petrovich Golubyatnikov, 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: A.A. Makhnev, I.N. Belousov, M.P. Golubyatnikov. On Q-polynomial Shilla graphs with b = 4, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 2, pp. 176–186.
[References -> on the "English" button bottom right]
