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.