On the Non-existence of Even Degree Graphs with Diameter 2 and Defect 2

Miller, M., Nguyen, M.H. and Pineda-Villavicencio, G.

    Using eigenvalue analysis, it was shown by Erdos et al. 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, when d is even, and we conjecture that they do not exist for any even d greater than 4.
Cite as: Miller, M., Nguyen, M.H. and Pineda-Villavicencio, G. (2008). On the Non-existence of Even Degree Graphs with Diameter 2 and Defect 2. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds. ACS. 93-95.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS