 TOPICS  # Moore Graph 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).

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 More things to try:

## References

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

Moore Graph

## Cite this as:

Weisstein, Eric W. "Moore Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MooreGraph.html