A005007 Number of cubic (i.e., regular of degree 3) generalized Moore graphs with 2n nodes. (Formerly M0199)

0, 1, 2, 2, 1, 2, 7, 6, 1, 1, 0, 1, 2, 9, 40, 56, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0

Offset

1,3

Comments

A generalized Moore graph is a regular graph of degree r where the counts of vertices at each distance from any vertex are 1, r, r(r-1), r(r-1)^2, r(r-1)^3, ... with the last distance having every other vertex. 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. Or, the average distance between pairs of vertices achieves the naive lower bound. As far as I know, it is an open problem if there are infinitely many generalized Moore graphs of each degree. - Brendan McKay, Oct 06 2003

a(35)>=1. a(n)=0 for n=94-112 and n=190-202. It is unknown if there are infinitely many. - Brendan McKay, May 02 2025

References

B. D. McKay and R. G. Stanton, The current status of the generalized Moore graph problem, pp. 21-31 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=1..32.

Brendan McKay, Emails to N. J. A. Sloane, 1991

Eric Weisstein's World of Mathematics, Generalized Moore Graph

Example

The counts are for graphs with 2, 4, 6, 8, ... nodes. In particular, there is a unique graph with 10 nodes.

Crossrefs

Sequence in context: A226328 A307599 A162663 * A395987 A188792 A192395

Adjacent sequences: A005004 A005005 A005006 * A005008 A005009 A005010

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Terms a(16)-a(32) from Brendan McKay, May 02 2025

Status

approved