2
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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
    Commented Jun 29, 2013 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
    Commented Jun 30, 2013 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
    Commented Jun 30, 2013 at 23:25

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi @Ira Gessel, I was curious if there is any known closed form formula for enumerating labelled 2-regular graphs ? $\endgroup$
    – SagarM
    Commented Apr 27, 2021 at 15:49
  • 1
    $\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
    Commented Apr 27, 2021 at 16:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .