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

[Jernej Azarija]

Dear Brendan,

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

:{hApo}?@@O?GM?CAqq at EAEBo_WQCDCOooeGHDPOoaWMGRPxEMIDpp_uOMFqP`ASLGx_?CCBA at Oo
[OHDAp_s[NGCSaUcRIDQp[oXLEr`s{^OGSQLGdrH{aTPgsYLEbPgsYLEbPgsYLEbP

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.

Best,

Jernej



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

> 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
>>
>
>