On the Nonexistence of Graphs of Diameter \(2\) and Defect \(2\)

Mirka Miller1,2, Minh Hoang Nguyen3, Guillermo Pineda-Villavicencio4,5
1Department of Mathematics University of West Bohemia Univerzitni 22, 306 14 Pilsen, Czech Republic
2School of Electrical Engineering and Computer Science The University of Newcastle Callaghan, New South Wales 2308, Australia
3Bricsson Managed Service Global Service Delivery Centre – Ericsson 112-118 Talavera Road, North Ryde New South Wales 2113, Australia
4School of Information Technology and Mathematical Sciences University of Ballarat Mount Helen, Victoria 3353, Australia
5Department of Computer Science University of Oriente Ave. Patricio Lumumba S/N, Santiago de Cuba 90500 Cuba

Abstract

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 \geq 6\), and conjecture that they do not exist for any \(d \geq 6\).