A Moore graph of type 
is a regular graph of vertex
degree 
and girth 
that contains the maximum possible number of nodes, namely
 |
(1)
|
(Bannai and Ito 1973; Royle).
Equivalently, it is a 
-cage graph, where 
is the vertex degree and 
is the girth, with an excess
of zero (Wong 1982). Moore graphs are also called minimal 
-graphs (Wong 1982), and are always distance-regular.
The numbers of Moore graphs on 
, 2, ... nodes are 0, 0, 0, 1, 1, 2, 1, 2, 1, 3, 1, 2, 1,
.... The following table lists some Moore graphs (excluding complete and complete
bipartite graphs).
 | named Moore graphs (or reference) |
 | Petersen graph |
 | Heawood graph |
 | Tutte 8-cage |
 | Wong (1982) |
 | order-4 generalized triangle |
 | Hoffman-Singleton graph |
Hoffman and Singleton (1960) first used the term "Moore graph" while looking at related regular 
graphs of a given vertex degree 
and diameter 
. They showed that there is a unique Moore graph for types
(Petersen
graph) and 
(Hoffman-Singleton graph), where 
is the graph
diameter, but no other 
Moore graphs with the possible exception of 
(Bannai and Ito 1973). Bannai and Ito (1973) subsequently
showed that there exist no Moore graphs of type 
with girth 
and valence 
. Equivalently, a 
-Moore graph exists only if (1) 
and 
, 7, or (possibly) 57, or (2) 
, 8, or 12 (Wong 1982). This settled the existence and uniqueness
problem from finite Moore graphs with the exception of the case 
, which is still open. A proof of this theorem, sometimes
called the Hoffman-Singleton theorem,
is difficult (Hoffman and Singleton 1960, Feit and Higman 1964, Damerell 1973, Bannai
and Ito 1973), but can be found in Biggs (1993).
