Publications of (and about) Paul Erdös
Autor: Erdös, Paul; Fajtlowicz, Siemion; Hoffman, Alan J.
Title: Maximum degree in graphs of diameter 2. (In English)
Source: Networks 10, 87-90 (1980).
Review: It is well known that there are at most four Moore graphs of diameter 2, i.e., graphs of diameter 2, maximum degree d, and d2+1 vertices. The purpose of this paper is to prove that with the exception of C4, there are no graphs of diameter 2, of maximum degree d, and with d2 vertices.
Classif.: * 05C35 Extremal problems (graph theory)
05C38 Paths and cycles
Keywords: Moore graphs; diameter; maximum degree
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag