- Title
- Complete catalogue of graphs of maximum degree 3 and defect at most 4
- Creator
- Miller, Mirka; Pineda-Villavicencio, Guillermo
- Date
- 2009
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/44848
- Identifier
- vital:1939
- Identifier
-
https://doi.org/10.1016/j.dam.2009.04.021
- Identifier
- ISSN:0166-218X
- Abstract
- We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M3,D, that is, (3,D,−)-graphs for ≤4. We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−)-graphs with D≥2 and ≤4. Our results also give an improvement to the upper bound on the largest possible number N3,D of vertices in a graph of maximum degree 3 and diameter D, so that N3,D≤M3,D−6 for D≥5. Copyright Elsevier.
- Relation
- Discrete Applied Mathematics Vol. 157, no. 13 (2009), p. 2983-2996
- Rights
- Copyright Elsevier
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- Cubic graphs; Degree/diameter problem; Moore bound; Moore graphs
- Full Text
- Reviewed
- Hits: 950
- Visitors: 1090
- Downloads: 158
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | DS1 | Accepted version | 313 KB | Adobe Acrobat PDF | View Details Download |