[Nauty] Embedding a 2-regular graph and canonical augmentation

Jernej Azarija jernej.azarija at gmail.com
Sat Dec 5 09:31:57 AEDT 2015


Hello,

this question is only indirectly related to nauty. I hope it's still on
topic but please let me know if its not appropriate.

I have a graph G with independent sets A, B comprised of 18 vertices each.
The vertices in A can be assumed to form an orbit of Aut(G). There is no
edge between A and B and I need to generate all non-isomorphic extensions
of G such that A \cup B induces a bipartite 2-regular graph in the natural
way (A,B remain independent sets). I am still figuring out the details of
the canonical augmentation method hence I wanted to ask

- What would be the best way to use this method here (that is, what is the
proper criterion for rejection)?

Also, since the required structure is really simple and the vertices of A
are indistinguishable, is there a more clever way to generate all such
graphs?


Best,

Jernej


More information about the Nauty mailing list