Welcome to MathOverflow

Question

6

2

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?

edited Oct 10 2011 at 20:55

jc
3,885●9●23

asked Oct 10 2011 at 19:30

John Young
173●5

1

Why the "of course"? – Richard Kent Oct 10 2011 at 19:36

Because he defines "graph" as "simple graph", I am guessing. – Igor Rivin Oct 10 2011 at 19:38

This question appeared before on MO: mathoverflow.net/questions/22089/… – Andy B Oct 11 2011 at 16:03

Thanks for your comment! – John Young Oct 11 2011 at 17:24

Brendan McKay · Accepted Answer · 2011-10-10 23:28:28Z UTC

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

Igor Rivin · Answer 2 · 2011-10-10 19:37:52Z UTC

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).

Tony Huynh · Answer 3 · 2011-10-10 19:45:59Z UTC

3

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.

answered Oct 10 2011 at 19:45

Tony Huynh
8,863●1●22●62

nvcleemp · Answer 4 · 2011-10-11 06:59:09Z UTC

1

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

answered Oct 11 2011 at 6:59

nvcleemp
259●7

How many $p$-regular graphs with $n$ vertices are there?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.