# How many graphs of order n, maximum degree k, and maximum diameter d exist?

The total number of simple undirected graphs of order $$n$$ is

$$\sum\limits_{i = 0}^{\frac{n(n-1)}{2}}{\binom{\frac{n(n-1)}{2}}{i}} = 2^{\frac{n(n-1)}{2}}$$.

What is the number of simple undirected graphs (including isomorphisms) of order $$n$$, maximum degree $$k$$, and diameter at most $$d$$? Is there a similar, concise representation? Are there close bounds?

The maximum degree states, that every node can be connected to at most $$k$$ other nodes.

The maximum diameter states, that the length of the longest shortest path between two nodes must be at most $$d$$ (i.e., each nodes eccentricity is at most $$d$$).

Since it is not yet known whether, e.g., a graph with $$n=3250$$, $$d=2$$, $$k=57$$ exists, I do not expect an exact solution. However an approximation or bounds would be helpful.

Edit: Maybe a slightly different point of view helps: Assuming there exists at least one graph of order $$n$$, maximum degree $$k$$, and diameter at most $$d$$. How many more exist if we increase the maximum degree by one? A lower bound suffices.

• Is there any table of known graphs for small values of $d$, like $2$, $k$ and $n$? Oct 3, 2019 at 8:03