[Nauty] How to apply automorphisms?

[Brendan McKay]

Hi, I'm not sure exactly what you are asking.

Suppose we have graphs G and H.  By applying nauty to each of
G and H we can find an isomorphism phi from G to H.  We can also
find the orbits of Aut(G) and Aut(H) - these are given by the
parameter orbits[].   Then there is an isomorphism from G to H
that maps g in G onto h in H iff phi(g) lies in the same orbit
of Aut(H) as h lies in.

This means it is very efficient to ask this question for many g and h
once nauty has been called separately for G and H.  In case you only
want to ask this question for a single g in G and h in H, you can
use the method that Guenter suggested.  Call nauty for G with an
initial colouring (partition) [ g | everything else] and call nauty
for H with initial colouring (partition) [ h | everything else].
Then there is an isomorphism mapping g onto h iff the canonical
graphs are the same.

Brendan.


* Aisha Fenton <aishafenton at mac.com> [040728 21:01]:
> Hi,
> I'm currently using nauty to test a pair of graphs for an isomorphism. 
> However, now I have a requirement that once nauty has found a canonic 
> labeling for two isomorphic graphs (G, H)  I want to test if vertices v 
> in V(G) are ever mapped to y in V(H) under some automorphism.
> 
> That is, I have vertex boundary defined on each G and H. Once I have 
> found that G and H are isomorphic, I want to see if the boundary on G 
> is mappable to H (for some automorphism)
> 
> From the documentation the only way I could see was to parse the 
> automorphism output file, and then try each cycle - since I'm dealing 
> with hundreds of thousands of graphs, this method seemed like it 
> wouldn't be fast enough for me.
> 
> Also a newbie question. I'm not that versed in group theory, so I'd 
> really appreciate it if someone could give me a quick run down of how 
> I'm to interrupt the output automorphisms (I only need to know if 
> vertex x ever maps to vertex y). From my very basic group theory 
> knowledge, I was expecting the examples in the documentation of the 
> output automorphisms, to contain something like a rotation cycle 
> (01,2,3,4,5,6), but they don't?
> 
> 
> Thanks heaps,
> Aisha
>  
> 
> 
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list