A.A. Makhnev, I.N. Belousov, M.P. Golubyatnikov. On Q-polynomial Shilla graphs with b = 4 ... P. 176-186

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.