File(s) under permanent embargo
On the non-existence of odd degree graphs of diameter 2 and defect 2
conference contribution
posted on 2008-01-01, 00:00 authored by Brendan McKay, Mirka Miller, Minh Hoang Nguyen, Guillermo Pineda-VillavicencioIn 1960, Hoffman and Singleton investigated the existence of Moore
graphs for diameter and found that Moore graphs only exist for d =
2, 3, 7 and possibly 57. In 1980, Erd˝os et al. asked the following
more general question: Given nonnegative numbers d and ∆, is there
a (d, 2, ∆)-graph, that is, a graph of diameter 2, maximum degree d
and order d
2 + 1 − ∆?. Erd˝os et al. solved the case for ∆ = 1: the C4
is the only possible graph.
In this paper, we consider the next case (∆=2). We prove the nonexistence of such graphs for infinitely many values of odd d and we
conjecture that they do not exit for any odd d greater than 5.
graphs for diameter and found that Moore graphs only exist for d =
2, 3, 7 and possibly 57. In 1980, Erd˝os et al. asked the following
more general question: Given nonnegative numbers d and ∆, is there
a (d, 2, ∆)-graph, that is, a graph of diameter 2, maximum degree d
and order d
2 + 1 − ∆?. Erd˝os et al. solved the case for ∆ = 1: the C4
is the only possible graph.
In this paper, we consider the next case (∆=2). We prove the nonexistence of such graphs for infinitely many values of odd d and we
conjecture that they do not exit for any odd d greater than 5.
History
Event
Combinatorial Algorithms. International Workshop (18th : 2007 : Lake Macquarie, N.S.W.)Volume
10Series
Texts in algorithmicsPagination
1 - 11Publisher
College PublicationsLocation
Lake Macquarie, N.S.W.Place of publication
London, Eng.Start date
2007-11-05End date
2007-11-09ISBN-13
9781904987673ISBN-10
1904987672Language
engNotes
IWOCA proceedings; v.1Publication classification
E1.1 Full written paper - refereedCopyright notice
2008, College PublicationsEditor/Contributor(s)
L Brankovic, Y Lin, W SmythTitle of proceedings
IWOCA 2007 : Proceedings of the 18th International Workshop of Combinatorial Algorithms 2007Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC