Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
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. –  quid Jun 29 '13 at 21:33
    
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. –  Vince Vatter Jun 30 '13 at 9:49
    
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. –  Richard Stanley Jun 30 '13 at 23:25
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.