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).

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).

Aschbacher, M. "The Non-Existence of Rank Three Permutation Group of Degree 3250 and Subdegree 57." J. Algebra19, 538-540,
1971.Bannai, E. and Ito, T. "On Moore Graphs." J. Fac.
Sci. Univ. Tokyo Ser. A20, 191-208, 1973.Biggs, N. L.
Ch. 23 in Algebraic
Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Bosák,
J. "Cubic Moore Graphs." Mat. Časopis Sloven. Akad. Vied20,
72-80, 1970.Bosák, J. "Partially Directed Moore Graphs."
Math. Slovaca29, 181-196, 1979.Damerell, R. M. "On
Moore Graphs." Proc. Cambridge Philos. Soc.74, 227-236, 1973.Feit,
W. and Higman, G. "The Non-Existence of Certain Generalized Polygons."
J. Algebra1, 114-131, 1964.Friedman, H. D. "On
the Impossibility of Certain Moore graphs." J. Combin. Th. B10,
245-252, 1971.Godsil, C. D. "Problems in Algebraic Combinatorics."
Electronic J. Combinatorics2, No. 1, F1, 1-20, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1f1.html.Godsil,
C. and Royle, G. "Moore Graphs." §5.8 in Algebraic
Graph Theory. New York: Springer-Verlag, pp. 90-91, 2001.Hoffman,
A. J. and Singleton, R. R. "On Moore Graphs of Diameter 2 and 3."
IBM J. Res. Develop.4, 497-504, 1960.Royle, G. "Cages
of Higher Valency." http://www.csse.uwa.edu.au/~gordon/cages/allcages.html.Wong,
P. K. "Cages--A Survey." J. Graph Th.6, 1-22, 1982.