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

[Brendan McKay]

Consider the example you sent.  Vertices 0..17 are each fixed by the 
group, and 42..59 is an orbit.  Not only that but the action of Aut(G) 
on 42..59 is the full S_18 (which is good; the larger the better).

The number of inequivalent ways to insert a 2-regular bipartite graph 
between A and B is exactly 2,355,301,661,033,953, which is a bit large.  
So if you don't have strong rules for pruning cases during the 
generation there is no chance.

Take any fixed-point-free permutation on 0..17, say  (0 4)(1 2 7)(3 
12)...  and insert 42..59 into it in arbitrary order to make a 
collection of cycles, eg 0-42-4-43-0, 1-44-2-45-7-47-1, ...   All these 
are nonisomorphic in your example.  If the group is different the count 
could be higher or lower.

The generation process assuming more general possibilities for Aut(G):  
the expansion operation is to add one edge in a place allowed, and the 
reduction is to remove one A-B edge.  For expansion you have to find the 
orbits of the action of Aut(G) on the allowed pairs (x,y) where x is in 
A and y is in B.   You can do this by using the userautomproc hook to 
apply the generators to AxB.  After adding an edge, you need the orbits 
on AxB for the new graph again as well as a canonical labelling.  Reject 
the new graph unless the new edge is in the same orbit as the A-B edge 
with the lexicographically greatest new labelling.  To make it much 
faster, define the rejection criterion using an invariant before 
applying nauty and try not to perform expansions that are sure to be 
rejected.  (Eg. require the new edge to extend an existing A-B path 
rather than starting a new path, when possible.)

Brendan.

On 5/12/2015 9:20 PM, Jernej Azarija wrote:
> 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 <mailto: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 <mailto:Nauty at anu.edu.au>
>         http://mailman.anu.edu.au/mailman/listinfo/nauty
>
>
>