Wednesday, 11 January 2012

recreational mathematics - 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

No comments:

Post a Comment