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. |
(local if available)