Moore Graph


A Moore graph of type (v,g) is a regular graph of vertex degree v>2 and girth g that contains the maximum possible number of nodes, namely

 n(v,g)={1+(v-1)^(g/2-1)+vsum_(r=0)^((g-4)/2)(v-1)^r   for g even; 1+vsum_(r=0)^((g-3)/2)(v-1)^r   for g odd

(Bannai and Ito 1973; Royle).

Equivalently, it is a (v,g)-cage graph, where v is the vertex degree and g is the girth, with an excess of zero (Wong 1982). Moore graphs are also called minimal (v,g)-graphs (Wong 1982), and are always distance-regular.

The numbers of Moore graphs on n=1, 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 (v,d) graphs of a given vertex degree v and diameter d. They showed that there is a unique Moore graph for types (v,d)=(3,2) (Petersen graph) and (7,2) (Hoffman-Singleton graph), where d is the graph diameter, but no other (v,d=2) Moore graphs with the possible exception of (57,d=2) (Bannai and Ito 1973). Bannai and Ito (1973) subsequently showed that there exist no Moore graphs of type (v,g) with girth g>=4 and valence v>2. Equivalently, a (v,g)-Moore graph exists only if (1) g=5 and v=3, 7, or (possibly) 57, or (2) g=6, 8, or 12 (Wong 1982). This settled the existence and uniqueness problem from finite Moore graphs with the exception of the case (57,2), 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).

See also

Cage Graph, Degree-Diameter Problem, Distance-Regular Graph, Generalized Moore Graph, Generalized Polygon, Girth, Heawood Graph, Hoffman-Singleton Graph, Hoffman-Singleton Theorem, Petersen Graph, Regular Graph, Tutte 8-Cage

Explore with Wolfram|Alpha


Aschbacher, M. "The Non-Existence of Rank Three Permutation Group of Degree 3250 and Subdegree 57." J. Algebra 19, 538-540, 1971.Bannai, E. and Ito, T. "On Moore Graphs." J. Fac. Sci. Univ. Tokyo Ser. A 20, 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. Vied 20, 72-80, 1970.Bosák, J. "Partially Directed Moore Graphs." Math. Slovaca 29, 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. Algebra 1, 114-131, 1964.Friedman, H. D. "On the Impossibility of Certain Moore graphs." J. Combin. Th. B 10, 245-252, 1971.Godsil, C. D. "Problems in Algebraic Combinatorics." Electronic J. Combinatorics 2, No. 1, F1, 1-20, 1995., 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.", P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

Referenced on Wolfram|Alpha

Moore Graph

Cite this as:

Weisstein, Eric W. "Moore Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications