Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/916879

OpenURL Link
Title
On the nonexistence of graphs of diameter 2 and defect 2
Author/Creator
Miller, Mirka;  Nguyen, Minh Hoang;  Pineda-Villavicencio, Guillermo
Institution
The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description
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 C₄ , 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.
Relation
Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, p. 5-20
Relation
http://www.charlesbabbage.org
Date
2009
Publisher
Charles Babbage Research Centre
Keyword(s)
graph theory;  vertices;  eigenvalue;  diameter
Resource Type
journal article
Identifier
http://hdl.handle.net/1959.13/916879
Identifier
ISSN:0835-3026
Reviewed
Reviewed
10 Visitors 12 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"Journal of Combinatorial Mathematics and Combinatorial Computing"
 
OR