Graph and permutation problem

Question

I have a graph (with nodes and edges) containing symmetry and a group of permutations to label the nodes so no edges are changed (automorphisms). Now I would like to determine for which nodes a permutation exchanges two equivalent (i.e. nodes with the same color or symmetry class) neighboring nodes.

When the nodes with equivalent neighbors stay the same, simply checking if the neighbors are exchanged in the permutation is enough. However, when the nodes with equivalent neighbors are also permuted (i.e. there are multiple nodes with the same color/symmetry class with the same equivalent neighbors), the problem becomes more complex.

Is there any known algorithm for such a problem?

Some remarks: The graph has no coordinates, it's a topology only

An example:

Identity permutation: http://imagebin.ca/view/2vAOi0I.html

There are 384 automorphic permutations: http://pastebin.org/157954

Simple example where the permutation inverts nodes 5 & 23: http://imagebin.ca/view/myQCvZnp.html

As long as 5 and 23 remain in the same place it is easy to determine if they are inverted (compared to the identity permutation). However, when these points are also interchanged it becomes more difficult.

Difficult example, permutation 67: http://imagebin.ca/view/9gl-Wmzt.html

Answer 1

I don't think your problem is well-defined. Imagine the following graph:

      1
     / \
    /   \
   2     3
  / \   / \
 4   5 6   7

Now consider the two automorphisms that swap the two subtrees of 1. automorphism A: 1<->1, 2<->3, 4<->6, and 5<->7 automorphism B: 1<->1, 2<->3, 4<->7, and 5<->6

Which one of these "inverts" the children of 2? Because 2 gets mapped to 3, we have to decide whether the natural correspondence is 4-6 and 5-7, or 4-7 and 5-6. But we have no information we can use to decide this fact.