M.P. Golubyatnikov. Distance-regular graphs with intersection arrays {104, 70, 25; 1, 7, 80} and {272, 210, 49; 1, 15, 224} do not exist ... P. 98-105

I.N. Belousov, A.A. Makhnev, and M.S. Nirova in 2019 described $Q$-polynomial distance-regular graphs $\Gamma$ of diameter 3 with strongly regular graphs $\Gamma_2$ and $\Gamma_3$, where the graphs $\Gamma_2$ and $\Gamma_3$ have the same vertices as $\Gamma$ and these vertices are adjacent if and only if they are at distance $2$ or $3$, respectively. Some of the $Q$-polynomial distance-regular graphs $\Gamma$ with strongly regular graphs $\Gamma_2$ and $\Gamma_3$ have intersection arrays
$$\left\lbrace \frac{(s^2+su-1)(u^2-1)}{s^2-1},\frac{(u^2-s^2)su}{s^2-1},u^2;1,\frac{u^2-s^2}{s^2-1},\frac{su^3-su}{s^2-1}\right\rbrace.$$
For small values of $s$ and $u$,  we have intersection arrays $\{104,70,25;1,7,80\}$ ($u=5$, $s=2$) and $\{272,210,49;1,15,224\}$ ($u=7$, $s=2$). We prove that distance-regular graphs with such arrays do not exist. We also study the properties of a local subgraph in a hypothetical distance-regular graph with intersection array $\{399, 320, 64; 1, 20, 336\}$ ($u=8$, $s=2$).

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

Received March 13, 2020

Revised October 21, 2020

Accepted October 26, 2020

Funding Agency: This work was supported by the Russian Science Foundation (project no. 19-71-10067).

Mikhail Petrovich Golubyatnikov, doctoral student, 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.   Belousov I.N., Makhnev A.A., Nirova M.S. On $Q$-polynomial distance-regular graphs $\Gamma_2$ and $\Gamma_3$. Sib. Elektron. Mat. Izv., 2019, vol. 16, pp. 1385–1392 (in Russian). doi: 10.33048/semi.2019.16.096 

2.   Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; N Y: Springer-Verlag, 1989, 495 p. ISBN: 0387506195 .

3.   Coolsaet K., Jurishich A. Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs. J. Comb. Theory, Ser. A, 2008, vol. 115, no. 6, pp. 1086–1095. doi: 10.1016/j.jcta.2007.12.001 

4.   Gavrilyuk A.L., Koolen J.H. The Terwilliger polynomial of a $Q$-polynomial distance-regular graph and its application to pseudo-partition graphs. Linear Algebra Appl., 2015, vol. 466, pp. 117–140. doi: 10.1016/j.laa.2014.09.048 

Cite this article as: M.P. Golubyatnikov. Distance-regular graphs with intersection arrays {104,70,25;1,7,80} and {272,210,49;1,15,224} do not exist, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2020, vol. 26, no. 4, pp. 98–105.