L
lcz
Guest
lcz Asks: Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence?
I know the following problem is famous:
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
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.
I know
It is not clear if there is an alternative math software, or if there is a later version of
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
.- 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.
- http://www.mathe2.uni-bayreuth.de/thomas_g/gradpart.html
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.SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.