Codes in Shilla distance-regular graphs
I. N. Belousovab a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg
Abstract:
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.
UDC:
519.17
MSC: 05C25 Received: 25.12.2017
DOI:
10.21538/0134-4889-2018-24-2-34-39