# Find all non-isomorphic graphs with a particular degree sequence

I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible.

The only way I found is generating the first graph using the Havel-Hakimi algorithm and then get other graphs by permuting all pairs of edges and trying to use an edge switching operation (E={{v1,v2},{v3,v4}}, E'= {{v1,v3},{v2,v4}}; this does not change vertice degree).

Are there any faster algorithms?

• @Juho That would be a meaningful problem. And a tough one -- I guess graph isomorphism reduces to it? (It's probably not by accident that big data/social network guys do not really sample properly when they sample...) – Raphael Apr 21 '16 at 18:41
• You can also use the configuration model to generate all graphs, though you still need to check for isomorphism. – Yuval Filmus Apr 26 '16 at 20:49

3. If your degree sequences are of length $n$ for some small $n$ (or you can afford to do a lot preprocessing), generate all $n$-vertex graphs. For this, you can either download them all from McKay's homepage, or use e.g., geng. If you have additional information, you might use an even more specific generator such as plantri (geng has options too). Once you have the graphs, iterate over them and check whether they have the right degree sequence.