Welcome to MathOverflow

Question

7

1

Fix numbers n,k. Is there a closed formula known for the number of k-regular graphs consisting of n edges? I have a method of enumerating k-regular graphs on n edges, and would like to have a number to compare the algorithm against.

flag	asked Apr 21 2010 at 18:22 Gwyn Whieldon 831●3●12

1

I don't think there's any closed form formula, but you can compare your results with the data in OEIS, such as here: research.att.com/~njas/sequences/A005638 (for 3-regular graphs) or here: research.att.com/~njas/sequences/A051031. This is indexed by the number of vertices, not edges, but of course for fixed k this is the same up to a factor of k/2. – Alon Amit Apr 21 2010 at 18:44

Andy B · Accepted Answer · 2010-04-21 20:15:11Z UTC

I think the answer is no, but I would consult the following link:

http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html

which contains tables of the sums of the numbers you are interested in. The author is very generous with sharing data that is not posted online.

Enumeration of Regular Graphs

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.