Deakin University
Browse

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-Villavicencio
In 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.

History

Event

Combinatorial Algorithms. International Workshop (18th : 2007 : Lake Macquarie, N.S.W.)

Volume

10

Series

Texts in algorithmics

Pagination

1 - 11

Publisher

College Publications

Location

Lake Macquarie, N.S.W.

Place of publication

London, Eng.

Start date

2007-11-05

End date

2007-11-09

ISBN-13

9781904987673

ISBN-10

1904987672

Language

eng

Notes

IWOCA proceedings; v.1

Publication classification

E1.1 Full written paper - refereed

Copyright notice

2008, College Publications

Editor/Contributor(s)

L Brankovic, Y Lin, W Smyth

Title of proceedings

IWOCA 2007 : Proceedings of the 18th International Workshop of Combinatorial Algorithms 2007

Usage metrics

    Research Publications

    Categories

    No categories selected

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC