On Codes in Distance-Regular Graphs of Diameter 3

Zhurtov, A. Kh. , Gerieva, Z. S.
Vladikavkaz Mathematical Journal 2025. Vol. 27. Issue 3.

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\)\eject\noindent 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.

Keywords: distance-regular graph, strongly regular graph, Shilla graph

+ References

The sole copyright holder of the published work is the Founder of the Vladikavkaz Mathematical Journal. The terms of use of this work are governed by an open license (Creative Commons Attribution-NonCommercial 4.0 International). The use of metadata of the scientific article, including the title, abstract, author information, references, identifiers, and other bibliographic description elements for subsequent unrestricted use, is carried out under the terms of the CC BY or CC0 open licenses.