On codes in distance-regular graphs of diameter $3$

A. Kh. Zhurtov, Z. S. Gerieva

Kabardino-Balkarian State University, 173 Chernyshevsky St., Nalchik 360004, Russia

Abstract: Let $\Gamma$ be a distance-regular graph of diameter $d$. For $i\in \{1,2,\ldots,d\}$ the graph $\Gamma_i$ is defined on the vertex set of $\Gamma$ and two vertices $u$, $w$ are adjacent in $\Gamma_i$ if and only if $d_\Gamma(u,w)=i$. The Shilla graph is a distance-regular graph of diameter $3$ with the eigenvalue $\theta_1=a_3$. For the Shilla graph the number $a=a_3$ divides $k$ and we set $b=b(\Gamma)=k/a$. The Shilla graph has intersection array $\{ab,(a+1)(b-1),b_2;c_1,c_2,a(b-1)\}$. Jurisic and Vidali found intersection arrays of distance-regular graphs of diameter $3$ containing the maximal locally regular $1$-code perfect with respect to the last neighborhood. Moreover, such graph $\Gamma$ has intersection arrays $\{a(p+1),cp,a+1;1,c,ap\}$ (and is a strongly regular graph $\Gamma_3$) or $\{a(p+1),(a+1)p,c;1,c,ap\}$ (and is a Shilla graph). In this manuscript we study graphs $\Gamma$ such that it contains the maximal locally regular $1$-code. For a distance-regular graph with intersection array $\{a^2,a^2-1,c;1,c,a(a-1)\}$ and $a<1000$, $c<1000$, the multiplicities of the eigenvalues are integer only in the cases $(a,c)=(3,4)$ (and $q^1_{13}<0$), $(a,c)=(5,3)$, $(a,c)=(9,18)$ (and $q^3_{33}<0$), $(a,c)=(21,49)$ (and $q^3_{33}<0$), $(a,c)=(21,9)$. Thus, only arrays $\{25,24,3;1,3,20\}$ and $\{(441,440,9;1,9,420)\}$ remain. Moreover, a distance-regular graph with intersection array $\{a^2,a^2-1,c;1,c,a(a-1)\}$ does not exist. As a consequence, distance-regular graphs with intersection arrays $\{25,24,3;1,3,20\}$ and $\{(441,440,9;1,9,420)\}$ do not exist.

Key words: distance-regular graph, strongly regular graph, Shilla graph.

UDC: 519.17

MSC: 05E30, 05C50

Received: 01.04.2025

DOI: 10.46698/e5951-0245-2570-i