On the non-existence of even degree graphs with diameter 2 and defect 2

Using eigenvalue analysis, it was shown by Erdös et al. that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d2 vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d2-1 vertices do not exist for most values of d, when d is even, and we conjecture that they do not exist for any even d greater than 4. © 2008, Australian Computer Society, Inc.