# How to express the symmetry of two subgraphs?

In graph $$G$$, to determine whether two vertices have the same status, we can look for orbits for these two vertices in the automorphism group of graph $$G$$.

By Mathematica, the automorphism group of the above graph is as follows:

PermutationGroup[{Cycles[{{6, 7}}], Cycles[{{4, 5}}],
Cycles[{{1, 2}}], Cycles[{{1, 4}, {2, 5}}], Cycles[{{8, 9}}]}]


Its orbit is as follows:

{{1, 2, 4, 5}, {3}, {6, 7}, {8, 9}}

So $$1$$, $$2$$, $$4$$ and $$5$$ have the same status. "Same status" is my own understanding, it means the element is in the same orbit in its automorphism group.

We are trying to broaden this problem a bit.

How can we use the automorphism group (or other things) of a graph to describe that two subgraphs have the same status in the graph?

But here "same status" of the two subgraphs is based on my intuition. I am not sure how to define it rigorously yet. For example, in the following graph, triangles $$T^1$$ and $$T^2$$ have the same status (symmetric); triangles $$T^4$$ and $$T^5$$ have the same status (symmetric).

Note that $$T_1:=, T_2=, T_3=,T_4=,T_5=$$.

Triangle $$T^1$$ is not symmetric with any of the three triangles $$T^3$$, $$T^4$$ and $$T^5$$. Ps: In the end, I would like to write a program to determine whether two subgraphs have the same status.

• When you say that two subgraphs of a graph $\Gamma$ have the same status do you mean that there is an automorphism of $\Gamma$ that maps one to the other? May 1 at 13:31
• Yes, I feel that what you said meets my expectations, but I don't know how to determine whether such an automorphism exists or how to find such an automorphism. It seems that we need to find all the automorphisms and then check whether they map the two subgraphs. May 1 at 13:37
• You can do that using existing software, such as GAP (with the GRAPE package for graph automorphism) or Magma. Just compute the automorphism group of the graph and then test whether there is an automorphism mapping the vertex set of one subgraph to the other. May 1 at 14:46
• Thank you for recommending nice softwares. Just from the automorphic map of a graph does not seem to reflect the symmetry of two subgraphs. For example, the subgraph $T^1$ and subgraph $\{\{4,5\},\{3,5\}\}$ . Obviously they cannot be said to be symmetric since the number of edges is different, but their vertices have an automorphism ((1,4)(2,5)). I hope I made it clear. Or I miss something. May 1 at 16:02
• Yes that's true. So you want to know if there is an element in the automorphism group that simultaneously maps a set of vertices to another set of vertices and also a set of edges to another set of edges. This is equivalent to testing whether the intersection of two cosets of different subgroups is non-empty. There is some discussion of this problem in GAP here. Of course if the group is not too big then you can just use a naive search. May 1 at 16:28

Let $$T_1$$ and $$T_2$$ be two subgraphs of $$G$$. Take two disjoint copies of your graph $$G_1$$ and $$G_2$$. Color the edges of $$T_1$$ in $$G_1$$, and the edges of $$T_2$$ in $$G_2$$.
Your subgraphs are equivalent if there exists an isomorphism between $$G_1$$ and $$G_2$$ that maps colored edges with colored edges, and non-colored edges with non colored edges.