I have been following a few papers on the asymptotic enumeration of $r$-regular graphs of $n$ vertices, $L_r$.

According to Random Graphs, $L_r = L_n \sim \sqrt{2} e^{- \frac{\left(r^2 - 1\right)}{4}} \left(\frac{r^{\frac{r}{2} e^{-\frac{r}{2}}}}{r!}\right)^n n^{\frac{r n}{2}}$.

According to Asymptotic enumeration by degree sequence of graphs with degrees $o(n^{1/2})$, $L_r = \frac{\left(n k\right)!}{\left(\frac{nk}{2}\right)! 2^{\frac{nk}{2}} \left(k !\right)^n} e^{\left(-\frac{k^2 -1}{4} - \frac{k^3}{12 n} + O \left(\frac{k^2}{n}\right)\right)}$ where $r = o\left(n^{\frac{1}{2}}\right)$.

According to ASYMPTOTIC ENUMERATION BY DEGREE SEQUENCE OF GRAPHS OF HIGH DEGREE, $L_r = \sqrt{2} \left(2 \pi n \lambda^{d+1} \left(1 - \lambda\right)^{n-d}\right)^{-\frac{n}{2}} e^{\left(\frac{-1 + 10 \lambda -10\lambda^2}{12 \lambda \left(1 - \lambda\right)} + O\left(n^{-\zeta}\right)\right)}$

Which one should I use?


The first formula is the one you want to use.

A $r$-regular graph is a specific case of a graph over a fixed degree sequence. Now with some assumptions on the degree sequence, you can get a formula enumerating the number of graphs over that sequence. And in particular, when the graph is $r$-regular the degree sequence has a nice form which simplifies to the first expression you gave. Brendan McKay's papers are concerned with relaxing the assumptions made on the degree sequence, which obviously complexifies the matter.


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.