On bipartite cages of excess 4 (Q521356)

Summary: The Moore bound \(M(k,g)\) is a lower bound on the order of \(k\)-regular graphs of girth \(g\) (denoted \((k,g)\)-graphs). The excess \(e\) of a \((k,g)\)-graph of order \(n\) is the difference \(n-M(k,g)\). In this paper we consider the existence of \((k,g)\)-bipartite graphs of excess \(4\) by studying spectral properties of their adjacency matrices. For a given graph \(G\) and for the integers \(i\) with \(0\leq i\leq \mathrm{diam}(G)\), the \(i\)-distance matrix \(A_i\) of \(G\) is an \(n\times n\) matrix such that the entry in position \((u,v)\) is \(1\) if the distance between the vertices \(u\) and \(v\) is \(i\), and zero otherwise.~We prove that the \((k,g)\)-bipartite graphs of excess \(4\) satisfy the equation \(kJ=(A+kI)(H_{d-1}(A)+E)\), where \(A=A_{1}\) denotes the adjacency matrix of the graph in question, \(J\) the \(n \times n\) all-ones matrix, \(E=A_{d+1}\) the adjacency matrix of a union of vertex-disjoint cycles, and \(H_{d-1}(x)\) is the Dickson polynomial of the second kind with parameter \(k-1\) and degree \(d-1\). We observe that the eigenvalues other than \(\pm k\) of these graphs are roots of the polynomials \(H_{d-1}(x)+\lambda\), where \(\lambda\) is an eigenvalue of \(E\). Based on the irreducibility of \(H_{d-1}(x)\pm 2\), we give necessary conditions for the existence of these graphs. If \(E\) is the adjacency matrix of a cycle of order \(n\), we call the corresponding graphs graphs with cyclic excess; if \(E\) is the adjacency matrix of a disjoint union of two cycles, we call the corresponding graphs graphs with bicyclic excess. In this paper we prove the non-existence of \((k,g)\)-graphs with cyclic excess \(4\) if \(k\geq 6\) and \(k \equiv 1\) (mod 3), \(g=8, 12, 16\) or \(k \equiv 2\) (mod 3), \(g=8\); and the non-existence of \((k,g)\)-graphs with bicyclic excess \(4\) if \(k\geq 7\) is an odd number and \(g=2d\) such that \(d\geq 4\) is even.