On graphs with cyclic defect or excess

zbMATH Open1204.05043arXiv1010.5841MaRDI QIDQ612923FDOQ612923

Authors: C. Delorme, Guillermo Pineda-Villavicencio 

Publication date: 16 December 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 {it graphs with defect or excess $epsilon$}, respectively. While {it 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 $nimesn$ 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 emph{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(frac643d^{3/2})$ for the number of graphs of odd degree $dge3$ 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 $dge3$ and cyclic defect or excess. Actually, we conjecture that, apart from the M"obius ladder on 8 vertices, no non-trivial graph of any degree $ge3$ and cyclic defect or excess exists.

Full work available at URL: https://arxiv.org/abs/1010.5841

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Nonexistence of graphs with cyclic defect
• On graphs with excess or defect 2
• On graphs of defect at most 2
• Graphs of diameter 2 with cyclic defect
• On bipartite cages of excess 4

zbMATH Keywords

defectMoore boundMoore graphexcessPell equationcyclic excessChebyshev polynomial of the second kindcyclic defect

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Cited In (10)

• Graphs of diameter 2 with cyclic defect
• On graphs of defect at most 2
• Nonexistence of graphs with cyclic defect
• On graphs of maximum degree 3 and defect 4
• A lower bound for the discriminant of polynomials related to Chebyshev polynomials
• Some defective parameters in graphs
• Counting cycles in graphs with small excess
• On graphs with excess or defect 2
• On bipartite cages of excess 4
• Moore graphs and cycles are extremal graphs for convex cycles

This page was built for publication: On graphs with cyclic defect or excess

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q612923)