MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the best known asymptotic formula for the number of graphs with a given degree sequence $(d_1, ... ,d_n)$, when the degrees are bounded by a constant and the number of vertices $n$ goes to infinity?

There are several papers of Mckay et al that provide bounds when the degrees are all $O(n^{\frac{1}{2}})$, but I am interested in bounded degrees, and I was hoping for more exact bounds for this special case. There are works on this as well, but they all seem to be pretty old, so I was wondering what the current state of the art is.

share|cite|improve this question
You can take the asymptotic formula for given degrees and sum it over all degrees within the bound. It isn't altogether trivial, but I'm pretty sure Nick Wormald did it somewhere. Sorry but I can't find it at the moment. – Brendan McKay Jul 11 '13 at 9:51
@BrendanMcKay doubtlessly knows more, but his paper with Catherine Greenhill seems very a propos... – Igor Rivin Jul 11 '13 at 13:54
Or maybe my memory was mistaken, since I was thinking of which has minimum degree not maximum degree. – Brendan McKay Jul 11 '13 at 16:08
up vote 3 down vote accepted

In my comment I was misreading the question, sorry. The situation for the real question is as follows. For very low degrees (say, at most 3) it isn't hard to get the exact number as a single or double summation. For the more general case of bounded maximum degree, the best asymptotic formula is my result with Wormald (Combinatorica, 11 (1991) 369-382), which in this case has an error term $O(1/n)$ where $n$ is the number of vertices of non-zero degree. It would be possible (though somewhat tedious) to find an explicit bound on the error term, but as far as I know nobody has done it. It would also be possible (in this special case of bounded degree) to obtain the precise term of order $1/n$ and have an error term of size $O(1/n^2)$. But, again, I think nobody has done it.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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