[Nauty] some re-usability of canonization

[ibrahim]

Dear Brendan

Ahh sad, thanks for the information. It was worth taking a shot at least :)
I hoped that you could resume the algorithm where it left of with the
super-graph but with a vertex less...

Thanks for the speedy answer!
Ibrahim


On 10/28/25 2:23 PM, Brendan McKay via Nauty wrote:
> Hi Ibrahim,
> 
> This is not possible with the canonical forms of either nauty or Traces.
> 
> A related comment: there is an old theorem whose author I have forgotten.
> Consider any two abstract groups G1 and G2.  Then there is a graph whose
> automorphism group is isomorphic to G1, but when one edge is removed
> its automorphism group is isomorphic to G2.  In other words, one edge
> can make an arbitrary amount of difference.
> 
> Brendan.
> 
> 
> On 28/10/2025 10:30 pm, ibrahim via Nauty wrote:
>> Dear all
>>
>> I have a second question related to some potential speed up for graph canonization.
>> Let's say I have a graph which I have computed the canonical graph of and let's say
>> I remove an edge or a vertex, (may not be possible with a vertex)
>> would it be possible to gain some time when canonicalizing this subgraph when
>> the supergraph has already been canonicalized somehow ? Or is that generally not possible
>> (either with Nauty or any other graph canonicalization library) ?
>>
>> Thanks once again
>> Ibrahim
>> _______________________________________________
>> Nauty mailing list
>> Nauty at anu.edu.au
>> https://mailman.anu.edu.au/mailman/listinfo/nauty
> 
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty