On graphs with cyclic defect or excess (Q612923)

Summary: The Moore bound constitutes both an upper bound on the order of a graph of maximum degree \(d\) and diameter \(D=k\) and a lower bound on the order of a graph of minimum degree d and odd girth \(g=2k+1\). Graphs missing or exceeding the Moore bound by \(\varepsilon\) are called graphs with defect or excess \(\varepsilon\), respectively. While Moore graphs (graphs with \(\varepsilon=0\)) and graphs with defect or excess 1 have been characterized almost completely, graphs with defect or excess 2 represent a wide unexplored area. Graphs with defect (excess) 2 satisfy the equation \(G_{d,k}(A)= J_n+B\) (\(G_{d,k}(A)= J_n-B\)), where \(A\) denotes the adjacency matrix of the graph in question, \(n\) its order, \(J_n\) the \(n\times n\) matrix whose entries are all 1's, \(B\) the adjacency matrix of a union of vertex-disjoint cycles, and \(G_{d,k}(x)\) a polynomial with integer coefficients such that the matrix \(G_{d,k}(A)\) gives the number of paths of length at most \(k\) joining each pair of vertices in the graph. In particular, if \(B\) is the adjacency matrix of a cycle of order \(n\) we call the corresponding graphs graphs with cyclic defect or excess; these graphs are the subject of our attention in this paper. We prove the non-existence of infinitely many such graphs. As the highlight of the paper we provide the asymptotic upper bound of \(O(\frac{64}{3}d^{3/2})\) for the number of graphs of odd degree \(d\geq 3\) and cyclic defect or excess. This bound is in fact quite generous, and as a way of illustration, we show the non-existence of some families of graphs of odd degree \(d\geq 3\) and cyclic defect or excess. Actually, we conjecture that, apart from the Möbius ladder on 8 vertices, no non-trivial graph of any degree \(\geq 3\) and cyclic defect or excess exists.