# Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence?

I know the following problem is famous:

• For a given degree sequence $$L$$ that is graphic, find an (efficient) algorithm to generate all of the nonisomorphic realizations of $$L$$.

This algorithm is sometimes helpful when we gather experimental evidence for conjectures (or as part of a proof).

There are many such articles, but the implementation of algorithms seems very few. I recently saw the following article, which provides the software gradpart.

But because the code was written around 1995, it is difficult for today's compilers to make it (due to the constant updating of the C++ standard).

I read the author's description and it looks like it can quickly generate all nonisomorphic graphs by a given degree sequence. In this example you can see a degree-partition with 50 vertices. Here we have 2 vertices of degree 1, 10 vertices of degree 2, 8 vertices of degree 3,... . Because of the use of the homomorphism-principle, during the generation we may obtain situations, where the operating group is trivial. So we get the possibility to describe large sets of pairwise non-isomorphic solutions implicitly. In this way in the shown example, we computed 34824038400 graphs in about 25 seconds and are also able to store these graphs with a very small amount of space.

I know nauty is great, but it seems not to offer this feature (except for generating regular graphs). Especially for cases with a slightly higher number of vertices (e.g. more than 15 vertices)

It is not clear if there is an alternative math software, or if there is a later version of gradpart for using it today. If there is an updated version of the software gradpart, we would love to see it play a role in the discovery of theorems.

• could you post the code somewhere, on github, say? I can't get it from their ftp (sic!) server :-( Jan 25 at 12:26
– lcz
Jan 25 at 12:43
• FWIW, I asked a similar question on Mathematica here: mathematica.stackexchange.com/q/170268/34893 where I also proposed a simple attempt, although it is a very inefficient one. Jan 25 at 13:15
– lcz
Jan 25 at 13:26
• Thanks - the README (LIESMICH - in German) basically says that one can make Gradpart in order not to build the GUI. That's a relief. However, the C++ dialect is very, very old, and apparently the code does not even use C++ STL (indeed, STL only appeared in 1994, and this code dates back to 1996). Instead there are home-made templates (in *.t files). Jan 25 at 20:50