File(s) under permanent embargo
On the nonexistence of graphs of diameter 2 and defect 2
journal contribution
posted on 2009-11-01, 00:00 authored by M Miller, M H Nguyen, G Pineda-VillavicencioIn 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.