On Graphs with Cyclic Defect or Excess

Abstract

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 $\epsilon$ are called graphs with defect or excess $\epsilon$, respectively.

While Moore graphs (graphs with $\epsilon=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}3d^{3/2})$ for the number of graphs of odd degree $d\ge3$ 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\ge3$ 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 $\ge 3$ and cyclic defect or excess exists.