Graph and permutation problem

Posted by user319771 on Stack Overflow See other posts from Stack Overflow or by user319771
Published on 2010-04-18T17:28:31Z Indexed on 2010/04/18 17:33 UTC
Read the original article Hit count: 408

Filed under:
|

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

© Stack Overflow or respective owner

Related posts about graph

Related posts about permutation