Inverse Problems in the Class of Distance-Regular Graphs of Diameter~$4$

A. A. Makhnev ; D. V. Paduchikh

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 1, pp. 199-208

Résumé

For a distance-regular graph $\Gamma$ of diameter 4, the graph $\Delta=\Gamma_{1,2}$ can be strongly regular. In this case, the graph $\Gamma_{3,4}$ is strongly regular and complementary to $\Delta$. Finding the intersection array of $\Gamma$ from the parameters of $\Gamma_{3,4}$ is an inverse problem. In the present paper, the inverse problem is solved in the case of an antipodal graph $\Gamma$ of diameter $4$. In this case, $r=2$ and $\Gamma_{3,4}$ is a strongly regular graph without triangles. Further, $\Gamma$ is an $AT4(p,q,r)$-graph only in the case $q=p+2$ and $r=2$. Earlier the authors proved that an $AT4(p,p+2,2)$-graph does not exist. A Krein graph is a strongly regular graph without triangles for which the equality in the Krein bound is attained (equivalently, $q^2_{22}=0$). A Krein graph $\mathrm{Kre}(r)$ with the second eigenvalue $r$ has parameters $((r^2+3r)^2,r^3+3r^2+r,0,r^2+r)$. For the graph $\mathrm{Kre}(r)$, the antineighborhood of a vertex is strongly regular with parameters $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$ and the intersection of the antineighborhoods of two adjacent vertices is strongly regularly with parameters $((r^2+2r)(r^2+2r-1),r^3+r^2-r,$ $0,r^2-r)$. Let $\Gamma$ be an antipodal graph of diameter 4, and let $\Delta=\Gamma_{3,4}$ be a strongly regular graph without triangles. In this paper it is proved that $\Delta$ cannot be a graph with parameters $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$, and if $\Delta$ is a graph with parameters $((r^2+2r)(r^2+2r-1),r^3+r^2-r,0,r^2-r)$, then $r>3$. It is proved that a distance-regular graph with intersection array $\{32,27,12(r-1)/r,1;1, 12/r,27,32\}$ exists only for $r=3$, and, for a graph with array $\{96,75,32(r-1)/r,1;1,32/r,75,96\}$, we have $r=2$.

Détail

Keywords: distance-regular graph, graph $\Gamma$ with strongly regular graph $\Gamma_{i,j}$.
Mots-clés : antipodal graph