A generalized Moore graph is a regular graph of degree 
where the counts of vertices
at each graph distance 
, 1, ... from any graph
vertex are 1, 
, 
, 
, 
, ..., 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 graph diameter is as little
as the naive bound allows. Stated yet another way, a generalized Moore graph is a
regular graph such that the mean
distance between pairs of vertices achieves the
naive lower bound.
The numbers of generalized Moore graphs of degree at least 3 with 
, 2, ... vertices
are 0, 0, 0, 1, 1, 4, 3, 13, 21, ... (OEIS A088933).
The numbers of cubic generalized Moore graphs with 
, 4, 6, ... vertices
are 0, 1, 2, 2, 1, 2, 7, 6, 1, 1, ... (OEIS A005007).
It is an open problem whether there are infinitely many generalized Moore graphs for each fixed degree 
.
