What is known about the number of labeled regular graphs on n vertices? The sequence does not appear to be in the OEIS.

  • 3
    $\begingroup$ Welcome to MO! Please include more details regarding what you want to know (exact numbers for samll values, bounds for somewhat larger ones, asymptotics [for which range of parameters])? Also, searching the internet one finds various information readily. I assume you already know quite a bit about the problem so it could be better to mention this so that people do not tell you things you already know. $\endgroup$ – user9072 Jun 29 '13 at 21:33
  • $\begingroup$ Do you mean the number of labeled $k$-regular graphs on $n$ vertices for any $k$? If so, I think you'd find more results by specifying a particular $k$. For example, $2$-regular labeled graphs seem to be counted by A001205. Also note that $3$-regular graphs are called trivalent. That helped me find A006607. $\endgroup$ – Vince Vatter Jun 30 '13 at 9:49
  • 1
    $\begingroup$ Enumerating labelled regular (simple) graphs of fixed degree $k$ on $n$ vertices is a notoriously intractable problem. Equivalently, one is enumerating traceless $n\times n$ symmetric $(0,1)$-matrices with row and column sums $k$. The paper of Musiker and Odama at mtholyoke.edu/courses/gcobb/REU_MCMC/papers.html deals with the situation when the matrices are not symmetric nor traceless, but their technique can be adapted to the present situation to give an answer of sorts, but not a very interesting one. $\endgroup$ – Richard Stanley Jun 30 '13 at 23:25

For fixed $k$, the problem of counting $k$-regular labeled graphs is not intractable at all; the counting sequence is P-recursive, so in principle the sequence is (up to a constant factor) as easy to compute as it could be. (But the complexity grows quickly with $k$.)

For $k\le 5$, see I. P. Goulden and D. M. Jackson, Labelled graphs with small vertex degrees and P-recursiveness. SIAM J. Algebraic Discrete Methods 7 (1986), 60-66.

and for P-recursiveness in the general case see my paper

Ira M. Gessel, Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A 53 (1990), 257-285.

  • $\begingroup$ Hi @Ira Gessel, I was curious if there is any known closed form formula for enumerating labelled 2-regular graphs ? $\endgroup$ – SagarM Apr 27 at 15:49
  • $\begingroup$ As Vince Vatter noted in his comment, 2-regular labeled graphs are counted by A001205 in the OEIS. There is an explicit formula there as a double sum. It's unlikely that there's a simpler formula. $\endgroup$ – Ira Gessel Apr 27 at 16:07

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.