Algorithm to calculate edge orbits of a graph

Question

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?

1. 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).

2. 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$.

3. 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?

Answer 1

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.

Answer 2

Having only the vertex orbits (instead of the full automorphism group) is not enough to compute the edge orbits. Consider, for example, a graph of $n=6$ vertices where all vertices are in a single orbit (in other words, the graph is vertex-transitive). From this information, you cannot differentiate whether your graph is

• $K_6$, which is also edge-transitive (all edges are in one orbit)
• the triangular prism, which is not edge-transitive
• or something else.

Answer 3

Yes your claim is correct for trees. Here is a standard fact about automorphism groups of trees:

Lemma: If $T$ is a finite tree then there is either a vertex or an edge fixed by every automorphism of $T$.

Sketch: (Dixon--Mortimer, exercise 9.2.4) Consider the function on vertices defined by $f(x) = \sum_{y \in V} d(x, y)$, where $d$ is graph distance. Clearly $\mathrm{Aut}(T)$ respects the values of $f$. You can show that $f$ is minimized uniquely either at a single vertex or at a pair of adjacent vertices. $\square$

Now assume there is a vertex $r$ fixed by $T$. Then you can think of $T$ as a rooted tree with root $r$, and each edge orbit is determined by the orbit of the vertex further from $r$. A similar argument applies if there is a fixed edge.

As others have commented, in general, edge orbits (orbitals) are not determined by vertex orbits, but they can be studied using the same tools. Studying a permutation group through its orbitals leads to the beautiful concept of coherent configurations.