Deakin University
Browse

File(s) under permanent embargo

On the nonexistence of graphs of diameter 2 and defect 2

Version 2 2024-06-05, 04:41
Version 1 2019-06-25, 11:55
journal contribution
posted on 2024-06-05, 04:41 authored by M Miller, MH Nguyen, G Pineda-Villavicencio
In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree d and d 2 +1 vertices), and found that such graphs exist only for d = 2,3,7 and possibly 57. In 1980, Erdó́s et al, using eigenvalue analysis, showed 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 with d ≤ 6, and conjecture that they do not exist for any d ≤ 6.

History

Journal

Journal of combinatorial mathematics and combinatorial computing

Volume

71

Pagination

5-20

Location

Winnipeg, Man.

ISSN

0835-3026

Language

eng

Publication classification

C1.1 Refereed article in a scholarly journal

Copyright notice

2009, Charles Babbage Research Centre

Publisher

Charles Babbage Research Centre