A Moore graph, named after E. F. Moore, 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
graphs and complete bipartite graphs).
Hoffman and Singleton (1960) introduced the term "Moore graph" because E. F. Moore had posed the problem of describing graphs attaining equality
in the degree-diameter bound. 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).
Moore graphs should not be confused with the Moore four-color graph, a 341-vertex planar graph used
as a test case for graph four-coloring.
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.Bermond, J.-C.;
Delorme, C.; and Quisquater, J.-J. "Strategies for Interconnection Networks:
Some Methods from Graph Theory." J. Parallel and Distributed Comput.3,
433-449, 1986.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."
Elec. J. Combin.2, No. 1, F1, 1-20, 1995. https://doi.org/10.37236/1224.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." https://web.archive.org/web/20090125032457/http://people.csse.uwa.edu.au/gordon/cages/allcages.html.Wong,
P. K. "Cages--A Survey." J. Graph Th.6, 1-22, 1982.
is a regular graph of
vertex degree 
and girth 
that contains the maximum possible number of nodes, namely
-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.
, 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
graphs and complete bipartite graphs).
-cage
(Wong 1982)
(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).
