I.N. Belousov. Codes in Shilla distance-regular graphs ... P. 34-39

Let $\Gamma$ be a distance-regular graph of diameter $3$ containing a maximal 1-code $C$, which is locally regular and perfect with respect to the last neighborhood. Then $\Gamma$ has intersection array $\{a(p+1),cp,a+1;1,c,ap\}$ or $\{a(p+1),(a+1)p,c;1,c,ap\}$, where $a=a_3$, $c=c_2$, and $p=p^3_{33}$ (Juri$\check{\mathrm{s}}$i$\acute{\mathrm{c}}$, Vidali). In the first case, $\Gamma$ has eigenvalue $\theta_2=-1$ and the graph $\Gamma_3$ is pseudogeometric for $GQ(p+1,a)$. In the second case, $\Gamma$ is a Shilla graph. We study Shilla graphs in which every two vertices at distance 2 belong to a maximal $1$-code. It is proved that, in the case $\theta_2=-1$, a graph with the specified property is either the Hamming graph $H(3,3)$ or a Johnson graph. We find necessary conditions for the existence of $Q$-polynomial Shilla graphs in which any two vertices at distance 3 lie in a maximal 1-code. In particular, we find two infinite families of feasible intersection arrays of $Q$-polynomial graphs with the specified property: $\{b(b^2-3b)/2,(b-2)(b-1)^2/2,(b-2)t/2;1,bt/2,(b^2-3b)(b-1)/2\}$ (graphs with $p^3_{33}=0$) and $\{b^2(b-4)/2,(b^2-4b+2)(b-1)/2,(b-2)l/2;1,bl/2,(b^2-4b)(b-1)/2\}$ (graphs with $p^3_{33}=1$).

Keywords: distance-regular graph, graph automorphism.

The paper was received by the Editorial Office on Dezember 25, 2017.

Funding Agency:

Russian Science Foundation (Grant Number 14-11-00061-П).

Ivan NIkolaevich Belousov, Cand. Sci. (Phis.-Math.), Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia: Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: i_belousov@mail.ru.


1.   Brouwer A.E., Cohen A.M., Neumaier A. Distance-Regular Graphs. Berlin; Heidelberg; N Y: Springer-Verlag, 1989, 495 p. ISBN: 0387506195 .

2.   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 .

3.   Vidali J. Kode v razdaljno regularnih grafih, Doctorska dissertacija, Univerza v Ljubljani, Ljubljana, 2013, 155 str.

4.   Jurisic A., Vidali J. Extremal 1-codes in distance-regular graphs of diameter 3. Des. Codes Cryptogr., 2012, vol. 65, no. 1-2, pp. 29–47. doi: 10.1007/s10623-012-9651-0 .

5.   Makhnev A.A., Nirova M.S. Shilla distance-regular graphs with $b_2 = c_2$. Mat. Zametki, 2018, vol. 103, no. 5, pp. 730–744 (in Russian). doi: 10.4213/mzm11503 .

6.   Makhnev A.A., Belousov I.N. To the theory of Shilla graphs with $b_2 = c_2$. Sib. Elektron. Mat. Izv., 2017, vol. 14, pp. 1135–1146 (in Russian). doi: 10.17377/semi.2017.14.097 .

7.   Koolen J.H., Park J., Yu H. An inequality involving the second largest and smallest eigenvalue of a distance-regular graph. Linear Algebra Appl., 2011, vol. 434, no. 12, pp. 2404–2412. doi: 10.1016/j.laa.2010.12.032 .