- Title
- On graphs with cyclic defect or excess
- Creator
- Delorme, Charles; Pineda-Villavicencio, Guillermo
- Date
- 2010
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/43415
- Identifier
- vital:3811
- Identifier
- ISSN:1077-8926
- 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 ε are called graphs with defect or excess ε, respectively. While Moore graphs (graphs with ε = 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 Gd,k(A) = Jn +B (Gd,k(A) = Jn - B), where A denotes the adjacency matrix of the graph in question, n its order, Jn the n × n matrix whose entries are all 1's, B the adjacency matrix of a union of vertex-disjoint cycles, and Gd,k(x) a polynomial with integer coefficients such that the matrix Gd,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(64/3 d3/2) for the number of graphs of odd degree d ≥ 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 ≥ 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 ≥ 3 and cyclic defect or excess exists.
- Relation
- Electronic Journal of Combinatorics Vol. 17, no. 1 (2010), p.
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- Chebyshev polynomial of the second kind; Cyclic defect; Cyclic excess; Defect; Excess; Moore bound; Moore graph; Pell equation
- Full Text
- Reviewed
- Hits: 718
- Visitors: 787
- Downloads: 80
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Submitted version | 316 KB | Adobe Acrobat PDF | View Details Download |