Vertex orbits are a well-known concept in Graph Theory: these are the equivalence classes of vertices under the automorphism group $Aut(G)$ of a graph $G$. In the example, circled vertices are equivalent in the graph.
I was wondering if the concept of edge orbits also exists and defined in the same spirit of equivalence as vertex orbits. Edges coloured equally would belong to the same edge orbit since they are equivalent.
If the concept exists and is defined similarly as vertex orbits, can edge orbits be computed using vertex orbits? I know there exist algorithms that calculate vertex orbits — there are efficient implementations of these in nauty. I'm mostly interested in calculating these edge orbits for trees: is the following "algorithm" to calculate edge orbits on a tree $T$ correct?
-
Let $\mathcal{O}=\{\mathcal{O}_1,\dots,\mathcal{O}_k\}$ be the set of vertex orbits of $T$. Obviously, $\mathcal{O}_i\subseteq V(T)$ (with equality only when $T$ is a 1-vertex or 2-vertex tree).
-
For every pair $(\mathcal{O}_i,\mathcal{O}_j)$ (for simplicity, $1\le i<j\le k$), set $\mathcal{E}_{ij}$ to be the set of all edges of $T$ where one endpoint is in $\mathcal{O}_i$ and the other in $\mathcal{O}_j$.
-
Define $$\mathcal{E}=\bigcup_{i<j} \mathcal{E}_{ij}$$ as the set of edge orbits of $T$.
By "correct algorithm" I mean: is the claim in (3) correct for trees?
Best Answer
The automorphism group is defined to be a permutation group acting as permutations of the vertices. It induces a permutation group acting as permutations of the edges: $\pi:V\to V$ induces $\pi:E\to E$ by $\pi(\{v,w\}) = \{\pi(v),\pi(w)\}$. What you call edge orbits are the orbits of this action on edges.
I don't believe you can just take the orbits on vertices and infer what the orbits on edges are. However, you can compute the edge orbits using nauty in essentially the same time. It's a bit advanced: you need to capture the generators using the userautomproc hook and convert them into their actions on the edges, updating the edge orbits as you go.