On graphs with cyclic defect or excess

Charles Delorme ; Guillermo Pineda-Villavicencio

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

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.

Détail

DOI : 10.37236/415

Classification : 05C12, 05C35, 05C50, 05C75
Mots-clés : Moore bound, Moore graph, defect, excess, Chebyshev polynomial of the second kind, cyclic defect, cyclic excess, Pell equation