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
REFERENCES
1. Koolen J.H., Park J. Shilla distance-regular graphs. Europ. J. Comb., 2010, vol. 31, no. 8, pp. 2064–2073. doi: 10.1016/j.ejc.2010.05.012
2. Jurisic A., Vidali J. Extremal 1-codes in distance-regular graphs of diameter 3. Des. Codes Cryptogr., 2012, vol. 65, pp. 29–47.
3. Belousov I.N. Shilla distance-regular graphs with $b_2 = sc_2$. Trudy Inst. Mat. i Mekh. UrO RAN, 2018, vol. 24, no. 3, pp. 16–26 (in Russian). 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, pp. 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, no. 1-2, pp. 49–54. doi: 10.1007/s10623-012-9695-1
6. Belousov I.N., Makhnev A.A. Distance-regular graph with intersection array {105,72,24;1,12,70} does not exist. Sib. Elektron. Mat. Izv., 2019, vol. 16, pp. 206–216 (in Russian). doi: 10.33048/semi.2019.16.012
7. Belousov I.N., Makhnev A.A. Distance-regular graphs with intersection arrays {42,30,12;1,6,28} and {60,45,8;1,12,50} do not exist. Sib. Elektron. Mat. Izv., 2018, vol. 15, pp. 1506–1512 (in Russian). 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.S. New families of Q-polynomial association schemes. J. Comb. Theory, Ser. A, 2011, vol. 118, no. 2, pp. 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, Ser. A, 2012, vol. 119, no. 1, pp. 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. Ljubljana: Univerza v Ljubljani, 2013, 155 p.
14. 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, pp. 709–716. doi: 10.1016/j.ejc.2004.04.005
15. Makhnev A.A., Belousov I.N., Golubyatnikov M.P., Nirova M.S. Three infinite families of Shilla graphs do not exist. Dokl. Ross. Akad. Nauk, 2021, vol. 498, no. 1, pp. 45–50 (in Russian). doi: 10.31857/S2686954321030115
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.
