On bipartite cages of excess 4

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). 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 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)\pm2$, 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. We prove the non-existence of (k,g)-graphs with cyclic excess 4 if k\geq 6 and k \equiv 1 \pmod 3, g=8, 12, 16 or k \equiv 2  \pmod 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.