5
$\begingroup$

The program nauty comes with gtools which contains, among others, several generation programs like geng, genbg, ... I was wondering whether there is some article or other source describing the details of the algorithm used. I assume that the technique described in 'Isomorph-free exhaustive generation' is used, but I was interested in knowing which construction operations are used for each class and which was the criterion to select the parent for a given graph.

The main reason I want to know this, is that I see that there is the possibility to write plugins for these generation programs, but I would like to know a bit more about the program details before I try to find efficient ways to bound the process to get to the specific structures I'm interested in.

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
8
$\begingroup$

MathOverflow is not a good place for questions like this. The best place for technical questions about nauty is the mailing list.

Anyway, the parent of a graph $G$ is a graph $G-v$ where $v$ is some vertex. In geng you can assume $v$ has the maximum degree in $G$. In genbg you can assume that $v$ is on the right side of $G$ and has the maximum degree there. In each case there is more to the story, but the details depend on the parameters and it doesn't strike me as a good idea to assume any more when writing plugins.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. The plugin was of course only one reason. Curiosity being the other. ;-) I will have a look at the mailing list. $\endgroup$
    – bart_m8
    Commented Jan 23, 2014 at 6:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .