I do recreational math from time to time, and I was wondering about a couple of graph enumeration issues.

First, is it possible to enumerate all simple graphs with a given degree sequence?

Second, is it possible to enumerate all valid degree sequences for simple graphs with a given number of vertices?

Based on my wikipedia surfing, we can use the Erdos-Gallai theorem to determine if a degree sequence is valid, but this doesn't really lend itself to enumerating valid degree sequences efficiently. Similarly, we can use the Havel-Hakimi algorithm to construct at least one graph for a given valid degree sequence, but this doesn't help to enumerate all graphs for that degree sequence.

My (admittedly uneducated) guess is that it might be possible to work backwards using the Havel-Hakimi condition to construct graphs by building them up in different ways. Any insight would be appreciated :D

  • 3
    $\begingroup$ There's no easy answer to the first question - for example, there's no explicit formula for the number of 3-regular graphs. $\endgroup$ – Chris Godsil Sep 3 '10 at 21:33
  • 1
    $\begingroup$ I don't understand the use of the term "recreational math". This seems to be a perfectly good graph theory question. $\endgroup$ – Emil Sep 6 '10 at 10:59
  • $\begingroup$ Well mainly I wrote that to get people to cut me a bit of slack if I used the wrong terminology. Graph theory isn't my field, and as I wrote, most of what I know about this problem was gleaned from Wikipedia. It turned out to be very hard after all though, so I feel much better about not being able to do it myself! $\endgroup$ – Josh Kuhn Sep 7 '10 at 19:08
  • $\begingroup$ By "enumerate", do you mean to count them or to generate all of them? $\endgroup$ – Szabolcs Horvát May 12 at 18:31
  • $\begingroup$ By enumerate I meant generate them all $\endgroup$ – Josh Kuhn May 14 at 17:35

Regarding the question of enumerating degree sequences. Richard Stanley's paper: A zonotope associated with graphical degree sequences, in Applied Geometry and Discrete Combinatorics, DIMACS Series in Discrete Mathematics, vol. 4, 1991, pp. 555-570. Deale with the problem of enumerating graphical degree sequences.

As Chris commented enumerating graphs with presecribed degree sequences can be hard. A recent paper of McKay entitled: Subgraphs of dense random graphs with specified degrees is a good place to start looking of what is known.

(Threshold graphs are precisely those graphs that are unique given their degree sequences.)

  • 3
    $\begingroup$ In my paper to which Gil refers, I consider ordered degree sequences. Thus I would regard (2,1,1), (1,2,1), and (1,1,2) as different degree sequences. The more standard definition of degree sequence considers these to be the same. The enumeration problem is then much harder. $\endgroup$ – Richard Stanley Sep 4 '10 at 1:42

Hello !!!

I read your post several weeks ago as I also wanted to enumerate degree sequences but did not know how. I still do not know how to enumerate the graphs with a given degree sequence, but I did find a paper about the enumeration of degree sequences :

Alley CATs in search of good homes (1994) by Frank Ruskey , Robert Cohen , Peter Eades , Aaron Scott http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

The authors provide an algorithm in Pascal that I was not able to get to work, and I ended up re-implementing it myself in a different way, following the same idea of reversing the "Havel-Hakimi recognition algorithm"

I recently sent it as a Sage patch if you want to use it (even though my answer is almost one year late) :-)




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.