Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose that there are $n$ vertices, we want to construct a regular graph with degree $p$, which, of course, is less than $n$. My question is how many possible such graphs can we get?

share|improve this question
1  
Why the "of course"? –  Richard Kent Oct 10 '11 at 19:36
    
Because he defines "graph" as "simple graph", I am guessing. –  Igor Rivin Oct 10 '11 at 19:38
1  
This question appeared before on MO: mathoverflow.net/questions/22089/enumeration-of-regular-graphs/… –  Andy B Oct 11 '11 at 16:03
    
Thanks for your comment! –  John Young Oct 11 '11 at 17:24

4 Answers 4

up vote 21 down vote accepted

McKay and Wormald conjectured that the number of simple $d$-regular graphs of order $n$ is asymptotically $$\sqrt 2 e^{1/4} (\lambda^\lambda(1-\lambda)^{1-\lambda})^{\binom n2}\binom{n-1}{d}^n,$$ where $\lambda=d/(n-1)$ and $d=d(n)$ is any integer function of $n$ with $1\le d\le n-2$ and $dn$ even.

Bender and Canfield, and independently Wormald, proved this for bounded $d$ in 1978, and Bollobás extended this to $d=O(\sqrt{\log n})$ in 1980.

McKay and Wormald proved the conjecture in 1990-1991 for $\min\{d,n-d\}=o(n^{1/2})$ [1], and $\min\{d,n-d\}>cn/\log n$ for constant $c>2/3$ [2]. These remain the best results.

The gap between these ranges remains unproved, though the computer says the conjecture is surely true there too. The formula apart from the $\sqrt2e^{1/4}$ has a simple combinatorial interpretation, and the universality of the constant $\sqrt2e^{1/4}$ is an enigma crying out for an explanation.

Incidentally this conjecture is for labelled regular graphs. For isomorphism classes, divide by $n!$ for $3\le d\le n-4$, since in that range almost all regular graphs have trivial automorphism groups (references on request). For $d=0,1,2,n-3,n-2,n-1$, this isn't true.

[1] Combinatorica, 11 (1991) 369-382. http://cs.anu.edu.au/~bdm/papers/nickcount.pdf

[2] European J. Combin., 11 (1990) 565-580. http://cs.anu.edu.au/~bdm/papers/highdeg.pdf

share|improve this answer

There is no closed formula (that anyone knows of), but there are asymptotic results, due to Bollobas, see A probabilistic proof of an asymptotic formula for the number of labelled regular graphs (1980) by B Bollobás (European Journal of Combinatorics) or Random Graphs (by the selfsame Bollobas).

share|improve this answer

Looking up OEIS, some related sequences are A005176 for the number of non-isomorphic regular graphs on $n$ vertices, and A005177 for the number non-isomorphic connected regular graphs on $n$ vertices.

share|improve this answer

And 'of course', if you really want those graphs you might have a look at genreg by Markus Meringer: http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html

share|improve this answer

Your Answer

 
discard

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.