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
- Grüner T, Laue R, Meringer M. Algorithms for group actions applied to graph generation[C]//Groups and Computation II. AMS, 1997, 28: 113-123.
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.
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.