Degree Sequences and Graph Enumeration 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
 A: 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.)
A: 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
