10
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 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, 2010 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, 2010 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, 2010 at 19:08
  • 1
    $\begingroup$ By "enumerate", do you mean to count them or to generate all of them? $\endgroup$
    – Szabolcs Horvát
    May 12, 2019 at 18:31
  • $\begingroup$ By enumerate I meant generate them all $\endgroup$
    – Josh Kuhn
    May 14, 2019 at 17:35

2 Answers 2

Reset to default
7
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
  • 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, 2010 at 1:42
3
$\begingroup$

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=10.1.1.51.6493

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) :-)

http://trac.sagemath.org/sage_trac/ticket/11584

Nathann

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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