3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there any table of known graphs for small values of $d$, like $2$, $k$ and $n$? $\endgroup$ – guest17 Oct 3 '19 at 8:03
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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