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 😀
Best Answer
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.)