On Bipartite \(Q\)-Polynomial Graphs of Diameter Not Greater than \(5\)

Bitkina, V. V. , Makhnev, A. A.
Vladikavkaz Mathematical Journal 2025. Vol. 27. Issue 3.

Abstract:
Let \(u\) be a vertex of a bipartite \(Q\)-polynomial distance-regular graph \(\Gamma\) of diameter \(D\ge 3\), \(\Sigma=\Gamma_D(u)\), and \(\Lambda=\Sigma_2\). Then \(\Lambda\) is a distance-regular \(Q\)-polynomial graph. In the cases \(D=4\) and \(D=5\) the graph \(\Lambda\) is strongly regular \(Q\)-polynomial. The half graph \(\Gamma_2\) is strongly regular and \(\Lambda\) is a neighbourhood of a vertex in the complement of \(\Gamma_2\). Therefore, a necessary condition for \(Q\)-polynomiality of \(\Gamma\) is the strong regularity of neighbourhoods and antineighbourhoods of vertices in \(\Lambda\). A bipartite distance-regular graph \(\Gamma\) of diameter \(D\in \{4,5\}\) is called almost \(Q\)-polynomial if neighbourhoods and antineighbourhoods of vertices in its half-graph are strongly regular. There are two admissible intersection arrays of \(Q\)-polynomial graphs: \(\{10,9,8,7,6;1,2,3,4,10\}\) (a folded 10-cube) and \(\{55,54,50,35,10;1,5,20,45,55\}\). These graphs have strongly regular graphs \(\Lambda\) (parameters \((126,25,8,4)\) and \((210,99,48,45)\)) and neighbourhoods of vertices in \(\Lambda\) (parameters \((25,8,4,2)\) and \((99,48,22,24)\)). There are two admissible intersection arrays corresponding to graphs on \(704\) vertices: \(\{26,25,24,2,1;1,2,24,25,26\}\) and \(\{36,34,32,4,1;1,4,32,34,36\}\). In this manuscript we study almost \(Q\)-polynomial graphs of diameter \(5\). We obtain that distance-regular graphs with intersection arrays \(\{26,25,24,2,1;1,2,24,25,26\}\) and \(\{36,35,32,4,1;1,4,32,35,36\}\) do not exist.

Keywords: distance-regular graph, \(Q\)-polynomial graph, bipartite graph

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.