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

Jernej Azarija jernej.azarija at gmail.com
Sat Dec 5 21:20:06 AEDT 2015

Dear Brendan,

perhaps let me clarify with an example. Let G be the graph of order 60
represented by the sparse6 string


If we take A = {0,...,17} and B = {42,..,59} then the subgraph induced by A
\cup B in G is an independent set. I need to generate all graphs out of G
such that every vertex in A has precisely two neighbors in B and vice
versa. That's what I meant by embedding a 2-regular graph in (A,B)

As it turns out for this family of graphs B is an orbit of Aut(G).

Motivation. By embedding a 2-regular graph in (A,B) and (A',B) for A' =
{18,..,35} one would obtain a candidate for an induced subgraph of a
(162,21,0,1) SRG. Experiments suggest that  such graphs do not seem to
survive the pruning phase.



On Sat, Dec 5, 2015 at 4:47 AM, Brendan McKay <Brendan.McKay at anu.edu.au>

> Hi Jernej,  It isn't clear to me what you mean by "extensions".  If all you
> want to do is add edges between A and B, then only a few cases will
> give a 2-regular graph with A an orbit. Namely, G will consist of 9
> 4-cycles, 6 6-cycles, 3 12-cycles, 2 18-cycles, or one 36-cycle.
> But maybe your problem is different; please clarify this.
> Brendan.
> On 5/12/2015 9:31 AM, Jernej Azarija wrote:
>> 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
>> _______________________________________________
>> Nauty mailing list
>> Nauty at anu.edu.au
>> http://mailman.anu.edu.au/mailman/listinfo/nauty

More information about the Nauty mailing list