[Nauty] some re-usability of canonization

[Brendan McKay]

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