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?
$\begingroup$ $\endgroup$
3 
- 1$\begingroup$ Why the "of course"? $\endgroup$Autumn Kent– Autumn Kent2011-10-10 19:36:26 +00:00Commented Oct 10, 2011 at 19:36
- 1$\begingroup$ Because he defines "graph" as "simple graph", I am guessing. $\endgroup$Igor Rivin– Igor Rivin2011-10-10 19:38:22 +00:00Commented Oct 10, 2011 at 19:38
- 1$\begingroup$ This question appeared before on MO: mathoverflow.net/questions/22089/enumeration-of-regular-graphs/… $\endgroup$Andy B– Andy B2011-10-11 16:03:36 +00:00Commented Oct 11, 2011 at 16:03
Add a comment |
5 Answers
$\begingroup$ $\endgroup$
5 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. https://users.cecs.anu.edu.au/~bdm/papers/nickcount.pdf
[2] European J. Combin., 11 (1990) 565-580. https://users.cecs.anu.edu.au/~bdm/papers/highdeg.pdf
ADDED in 2018: The "gap between those ranges" mentioned above was filled by Anita Liebenau and Nick Wormald [3]. Another proof, by Mikhail Isaev and myself, is not ready for distribution yet.
- $\begingroup$ Is there an asymptotic value for all d-regular graphs on n vertices (not necessarily simple)? $\endgroup$user24576– user245762014-08-23 19:36:35 +00:00Commented Aug 23, 2014 at 19:36
- $\begingroup$ @Amudhan: The sparse case is here: arxiv.org/abs/1303.4218 . $\endgroup$Brendan McKay– Brendan McKay2014-08-24 02:33:45 +00:00Commented Aug 24, 2014 at 2:33
- $\begingroup$ I am sorry, I am a bit confused about, what is the meaning of $d=d(n)$, why is it a function? is $d$ not fixed before hand ? $\endgroup$SagarM– SagarM2021-04-20 09:49:25 +00:00Commented Apr 20, 2021 at 9:49
- 1$\begingroup$ @SagarM $d$ could be fixed, but suppose you want the number of regular graphs with $n$ vertices and degree $d=n/2$? Then $d$ is not fixed. The most general case is to take $d$ to be a function of $n$. $\endgroup$Brendan McKay– Brendan McKay2021-04-20 12:20:17 +00:00Commented Apr 20, 2021 at 12:20
- $\begingroup$ Thanks, that clarifies it. $\endgroup$SagarM– SagarM2021-04-20 12:33:34 +00:00Commented Apr 20, 2021 at 12:33
$\begingroup$ $\endgroup$
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).
$\begingroup$ $\endgroup$
1 This paper
- Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459
provides an asymptotic expansion for the number of $k$-regular graphs on $n$ vertices... $$ SG(k)_n = \frac{(nk/e)^{nk/2}}{(k!)^n} \frac{e^{−(k^2−1)/4}}{ \sqrt{2}}\left( 2 - \frac{1}{6} (k^4-2k^2+3k-1)/(kn) + \mathcal{O}(n^{-2}))\right) $$
More terms are provided in the paper.
- 1$\begingroup$ It's a great paper, but note that $k$ must be constant since the error term depends on $k$. $\endgroup$Brendan McKay– Brendan McKay2025-04-28 09:20:27 +00:00Commented Apr 28 at 9:20
$\begingroup$ $\endgroup$
And 'of course', if you really want those graphs you might have a look at genreg by Markus Meringer: https://www.mathe2.uni-bayreuth.de/markus/reggraphs.html
