M.S. Nirova. Codes in distance-regular graphs with $\theta_2 = -1$

If a distance-regular graph $\Gamma$ of diameter 3 contains a maximal 1-code $C$ that is both locally regular and last subconstituent perfect, 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}}$ and Vidali). In 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 graphs with intersection array $\{a(p+1),cp,a+1;1,c,ap\}$ in which any two vertices at distance 3 are in a maximal 1-code. In particular, we find four new infinite families of intersection arrays: $\{a(a-2),(a-1)(a-3),a+1;1,a-1,a(a-3)\}$ for $a\ge 5$, $\{a(2a+3),2(a-1)(a+1),a+1;1,a-1,2a(a+1)\}$ for $a$ not congruent to $1$ modulo $3$, $\{a(2a-3),2(a-1)(a-2),a+1;1,a-1,2a(a-2)\}$ for even $a$ not congruent to $1$ modulo $3$, and $\{a(3a-4),(a-1)(3a-5),a+1;1,a-1,a(3a-5)\}$ for even $a$ congruent to 0 or 2 modulo 5.

Keywords: distance-regular graph, maximal code

The paper was received by the Editorial Office on June, 26, 2018.

Marina Sefovna Nirova, Cand. Sci. (Phys.-Math.), Kabardino-Balkarian State University named after H.M. Berbekov, Nal’chik, 360004 Russia, e-mail: nirova_m@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.   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 .

3.   Makhnev A.A., Nirova M.S. Distance-regular Shilla graphs with $b_2 = c_2$. Math. Notes, 2018, vol. 103, no. 5-6, pp. 780–792. doi: 10.1134/S0001434618050103 .

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

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

6.   Makhnev A.A. On graphs in which the Hoffman bound for cocliques equals the Cvetcovich bound. Dokl. Math., 2011, vol. 83, no. 3, pp. 340–343. doi: 10.1134/S106456241 .

7.   Makhnev A.A. Jr., Makhnev A.A. Ovoids and bipartite subgraphs in generalized quadrangles. Math. Notes, 2003, vol. 73, iss. 5-6, pp. 829–837. doi: 10.1023/A:102405391 .