6
$\begingroup$

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.

enter image description here

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.

enter image description here

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?

$\endgroup$
4
  • 1
    $\begingroup$ So is this a complicated way of saying that each edge orbit is the set of all edges between two vertex orbits? $\endgroup$ Feb 17, 2022 at 11:59
  • $\begingroup$ The orbits are an equivalence relation on the vertices. There is an equivalence relation on edges given by the orbitals. I know this from quantum automorphism groups but it works classically too. Cannot elaborate right now... paper by Teo Banica and I on "Frucht property" describes it (to some degree). $\endgroup$ Feb 17, 2022 at 12:08
  • $\begingroup$ @GordonRoyle, Yes, thanks for the heads up $\endgroup$ Feb 17, 2022 at 12:54
  • $\begingroup$ @JPMcCarthy, I believe you mean this paper. I've found it on arxiv here. I'm not a mathematician (if anything, computer scientist) and I don't think my training includes the necessary knowledge to understand your paper. Nevertheless, I'll try to understand the relevant bit for our discussion. Any elaboration on the topic will be greatly appreciated! $\endgroup$ Feb 17, 2022 at 12:59

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for the explanation. And yes, I agree that this is advanced. As long as my proposal does not even work on trees, I'll try implementing this. $\endgroup$ Feb 17, 2022 at 13:21
  • 1
    $\begingroup$ In the case of trees two edges are in the same edge orbit iff the multisets of the two vertex orbits of the edge endpoints are the same. Jukku's example shows that this is not true for general graphs. $\endgroup$ Feb 17, 2022 at 13:41
  • $\begingroup$ I was wondering... will we ever see this implemented in a future version of nauty? It might be very helpful to all nauty's users. Just asking! ;) $\endgroup$ Feb 19, 2022 at 14:36
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I can see your point. But your examples only include cyclic graphs. Could you include an example that is a tree, please? Thank you for including links (I didn't remember very well the definition of transitivity). $\endgroup$ Feb 17, 2022 at 13:22
  • 1
    $\begingroup$ Oh, I didn't notice you were specifically targeting trees. For them the situation is better as per Brendan's comment. (And vertex-transitive trees would be a rather simple family anyway.) $\endgroup$ Feb 17, 2022 at 13:51
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.