Online Version - Last Updated - 20 Jan 2012 |
 |
| Home |
| |
| Procedures and Resources for Authors |
|
| Information and Resources for Volume Editors |
| |
| Orders and Subscriptions |
| |
| Published Articles |
|
| Upcoming Volumes |
| |
| Contact Us |
| |
| Useful External Links |
| |
| CRPIT Site Search |
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.
(from crpit.com)
(local if available)
