- Title
- On the nonexistence of graphs of diameter 2 and defect 2
- Creator
- Miller, Mirka; Nguyen, Minh Hoang; Pineda-Villavicencio, Guillermo
- Date
- 2009
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/63442
- Identifier
- vital:3670
- Identifier
- ISSN:0835-3026
- Abstract
- In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree d and d² + 1 vertices), and found that such graphs exist only for d = 2; 3; 7 and possibly 57. In 1980, Erdös et al., using eigenvalue analysis, showed that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d² vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d² - 1 vertices do not exist for most values of d with d ≥ 6, and conjecture that they do not exist for any d ≥ 6.
- Publisher
- Charles Babbage Research Centre
- Relation
- The Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, no. (2009), p. 5-20
- Rights
- Copyright Charles Babbage Research Centre
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0101 Pure Mathematics; 0802 Computation Theory and Mathematics; Moore graphs; Degree/diameter problem; Diameter 2 and defect
- Reviewed
- Hits: 1643
- Visitors: 1665
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|