How to express the symmetry of two subgraphs?

Question

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:=[1231], T_2=[3453], T_3=[3673],T_4=[6786],T_5=[6796]$.

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.

Answer 1

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.

Nearly all graph isomorphism solvers support colors on vertices. For colors on edges, if it is not supported, a solution is to subdivide each edge, color each old vertices with a specific color, and color the remaining vertices following our edge colors. Here, you just have to subdivide the edges of the subgraphs, and to color the new vertices with a new color. The documentation of Nauty suggest an approach by layers. It seems to create much more vertices, but might be more efficient in practice.