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 $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 $d$. How many more exist if we increase the maximum degree by one? A lower bound suffices.

This paper by McKay and Wormald is a good place to look for asymptotic results for the bounded degree part of your question. Enumerating graphs of a given diameter seems very hard.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.