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

[Jernej Azarija]

Hey there,

yes that was a typo. I meant (162,21,0,3).

Best,

Jernej

On Sat, Dec 5, 2015 at 11:25 AM, Nathann Cohen <nathann.cohen at gmail.com>
wrote:

> Do you mean a (162,21,0,3) ?
>
> I don't think that a (162,21,0,1) exists.
>
> Nathann
>
> On 5 December 2015 at 11:20, Jernej Azarija <jernej.azarija at gmail.com>
> 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>
> > 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
> >>>
> >>
> >>
> > _______________________________________________
> > Nauty mailing list
> > Nauty at anu.edu.au
> > http://mailman.anu.edu.au/mailman/listinfo/nauty
>