10
$\begingroup$

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.

enter image description here

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.

$\endgroup$
9

1 Answer 1

8
$\begingroup$

As far as I am aware, there is no such program. Also, it needs care to interpret gradpart's claims. Gradpart can make counts greater than one graph per machine instruction, which proves that it doesn't individually construct each graph in memory. Instead it makes data structures which represent large subclasses of graphs. The mapping from these data structures to lists of graphs is relatively routine, but it isn't carried out.

$\endgroup$
6
  • $\begingroup$ Thank you for the reminder. I have not been able to use this software successfully, and thus I cannot check this. I don't know if Gradpart give a implementation for generating all non-isomorphic graphs with a given degree sequence. Perhaps I misunderstood their statement. $\endgroup$
    – L.C. Zhang
    Jan 25, 2023 at 5:57
  • 1
    $\begingroup$ @lcz I can't compile it either, and there is no documentation in the package. As far as I am aware (and I can be wrong) this program counts graphs rather than generates them. I'll post more here if I learn more. $\endgroup$ Jan 25, 2023 at 11:46
  • 1
    $\begingroup$ One probably would need to strip off its GUI to make it build. A 35-y.o. GUI in C++ is certainly easier to do from scratch than to build :-) $\endgroup$ Jan 25, 2023 at 12:20
  • 1
    $\begingroup$ @lcz Ok, I am told it could write the graphs. However that must have been much slower than counting them for the examples given. $\endgroup$ Jan 25, 2023 at 12:35
  • $\begingroup$ Probably modifying nauty to do the job (it should not be much harder than enumeration of the regular graphs) is more productive than trying to resurrect that code. (I commented above that the code provides a way to skip building GUI). $\endgroup$ Jan 26, 2023 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.