[Nauty-list] commuting isomorphisms

Brendan McKay bdm at cs.anu.edu.au
Sun Sep 13 02:57:14 EST 2009


Hi, 

I think your mail didn't get to the mailing list, perhaps because
you are subscribed under with a different email address.  But
this reply should make it.

Suppose you have one known isomorphism g:G1->G2; ask nauty. Then
every isomorphism has the form g*k for k in Aut(G2). So you want to
find k in Aut(G2) such that f1*g*k = g*k*f2 which is the same as
g^(-1)*f1*g*k = k*f2. Note that f3 = g^(-1)*f1*g is an automorphism
of G2, so the problem you want to solve is just about one group:
given f2,f3 in Aut(G2), find k in Aut(G2) such that f3*k = k*f2,
which the question of whether/how f2,f3 are conjugate in Aut(G2).
Nauty can find g and Aut(G2), but you'll need GAP, Magna, etc,
to do the conjugacy test.

Hope I understood the question correctly.

Brendan.


* Mathieu Dutour <Mathieu.Dutour at ens.fr> [090911 22:10]:
> Dear nauty world,
> 
> the nauty program computes automorphism group and isomorphisms between   
> graphs. Vertex colored graphs are allowed and recently there was an
> extension to consider sparse graphs.
> 
> Of course we need to consider other structures like vertex colored graphs
> and there are tricks here and there to reduce a problem to a vertex
> colored graph. However recently I ran out of my bag of tricks:
> 
> If G1 and G2 are edge colored graphs and f1 and f2 are two automorphisms
> of G1 and G2, the question is does there exist a graph isomorphism
> phi:G1--->G2 such that phi(f1(x)) = f2(phi(x)).
> 
> For the question of automorphism, I know how to compute the group of
> graph automorphism phi:G-->G such that phi(f(x)) = f(phi(x)). The method
> is simply to compute the automorphism group of the graph and to use a
> computer algebra system (like GAP or Magma) to compute the commutant.
> 
> But as far as I know those techniques do not apply to the isomorphism
> problem. Obviously such isomorphisms can be found by backtracking.
> But would it be possible to modify nauty so as to take care of this
> isomorphism. Nauty has been extended from graphs to sparse graphs
> (an extension I do not use) but I wonder why some further extensions
> have not been done.  
> 
> Ideally, one would take a function pointer and put as input but
> apparently this has not been done and I wonder if there are some
> fundamental obstacle.
> 
> Best,
> 
>   Mathieu




More information about the Nauty mailing list