A generalized Moore graph is a regular graph of degree 
where the counts of vertices at each distance 
, 1, ... from any 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
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.
The numbers of generalized Moore graphs with 
, 2, ... nodes are 0, 0, 0, 1, 1, 4, 3, 13, 21, ... (OEIS
A088933).
The numbers of cubic generalized Moore graphs with 
,
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.
