On the nonexistence of graphs of diameter 2 and defect 2
Mirka Miller, Minh Nguyen, Guillermo Pineda‐Villavicencio · FedUni ResearchOnline (Federation University Australia) · 2009
In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree d and d 2 +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 4, there are no graphs of diameter 2, maximum degree d and d 2 vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d 2 - 1 vertices do not exist for most values of d with d ≤ 6, and conjecture that they do not exist for any d ≤ 6.