TOPICS
Search

Generalized Moore Graph


A generalized Moore graph is a regular graph of degree r where the counts of vertices at each distance d=0, 1, ... from any vertex are 1, r, r(r-1), r(r-1)^2, r(r-1)^3, ..., with the last distance count not necessarily filled up. That is, all the levels are full except possibly the last which must have the rest. Alternatively, the girth is as great as the naive bound allows and the diameter is as little as the naive bound allows. Stated yet another way, a generalized Moore graph is a regular graph such that the average distance between pairs of vertices achieves the naive lower bound.

GeneralizedMooreGraphs

The numbers of generalized Moore graphs with n=1, 2, ... nodes are 0, 0, 0, 1, 1, 4, 3, 13, 21, ... (OEIS A088933).

GeneralizedMooreGraphsCubic

The numbers of cubic generalized Moore graphs with n=2, 4, 6, ... nodes are 0, 1, 2, 2, 1, 2, 7, 6, 1, 1, ... (OEIS A005007).

It is an open problem if there are infinitely many generalized Moore graphs of each degree.


See also

Moore Graph, Regular Graph

Explore with Wolfram|Alpha

References

McKay, B. D. and Stanton, R. G. "The Current Status of the Generalised Moore Graph Problem." In Combinatorial Mathematics VI: Proceedings of the Sixth Australia Conference on Combinatorial Mathematics, Armidale, Australia, August 1978. New York: Springer-Verlag, pp. 21-31, 1979.Sloane, N. J. A. Sequences A005007/M0199 and A088933 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Generalized Moore Graph

Cite this as:

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

Subject classifications