Computing the edge orbits of a graph (and discussing definitions)

Question

A (vertex) automorphism in a graph $G=(V,E)$ is a permutation $\sigma$ of the vertices that preserves adjacency, namely $\sigma(u) \sigma(v) \in E$ if and only if $uv \in E$. The automorphisms of a graph induce a partition of the vertices into orbits, where two vertices belong to the same orbit if and only if there exists an automorphism that takes one to the other. Intuitively, the orbits correspond to vertices that are structurally equivalent in the graph (one also says symmetrical). For example, in the left graph $G$ below, there are three orbits: $\{a\}$, $\{b\}$, and $\{c,d\}$.

The present question focuses on the analogue concept for edges. Several definitions of edge automorphisms seem to co-exist, which confuses me. For instance, Wolfram MathWorld (link) defines an edge automorphism as a permutation of the edges that preserves adjacency among the edges (where two edges are adjacent iff they share an endpoint). Accordingly, the edge automorphism group of a graph is defined as the vertex automorphism group of its line graph.

What troubles me with this definition is that edges such as $ab$ and $cd$ in graph $G$ end up being in the same orbit of the edge automorphism group even though they are not symmetrical, because the corresponding vertices in the line graph $L(G)$ are (see the right-side picture). In fact, this definition seems to clash with that of edge-transitive graphs, where the concept of automorphism relates to symmetry, not adjacency. For the sake of disambiguation, I will subsequently refer to these two versions of edge automorphisms as adjacency-based versus symmetry-based. Now, my questions:

1. Is there something wrong with my understanding of edge automorphisms, or is there inherently two different concepts considered in the literature? In the first case, please kindly point me to the mistake.

2. The actual motivation for posting the present question was to find a way to compute the symmetry-based version of the edge orbits of a given graph. Initially, I was computing them by reducing the problem to computing the vertex orbits of the line graph (as prescribed by the MathWorld definition), then calling standard automorphism routines on existing software like SageMath... until I realize that this was not what I wanted.

   Of course, I do not expect an efficient algorithm for this problem, but any conceptually simple algorithm or reduction to another natural question would be much appreciated.

3. (Bonus question.) In the particular case that the edges are properly colored, are there reasons to believe that there could be an efficient way to compute the symmetry-based, color-preserving edge orbits? In fact, I could not find anything related even to classical automorphisms of properly vertex-colored graphs, so any pointer related to this natural case is also welcome.

Answer 1

It turns out that yes, indeed, there are two possible definitions for edge-automorphisms... but it turns out that they almost always coincide so that it seems that people often get away with not making the distinction.

First, some notation. For a simple graph $G = (V,E)$ we let $\Gamma_V(G)$ define the group of automorpisms over the set of vertices $V$ that preserve $G$'s edge structure. Similarly, we define $\Gamma_E(G)$ to be the group of automorphisms over the set of edges $E$ that preserves $G$'s edge incidence structure.

For any vertex-automorphism $\pi \in \Gamma_V(G)$, we observe that there is a natural edge-automorphism $\pi':E \to E$ induced by $\pi$. Let $\Gamma'_V(G)$ denote the group of such induced edge-automorphisms.

Theorem: $\Gamma'_V(G)$ is isomorphic to $\Gamma_E(G)$ for all simple, connected $G$ with three or more vertices, with three exceptions: $K_4$, $K_4$ with one edge deleted, and the graph illustrated above within the question.

In other words, the example presented in the question happens to be on one of the very few graphs that make the distinction between $\Gamma_E(G)$ and $\Gamma_V'(G)$ important. Also, it is trivial to observe that this isomorphism does not hold for graphs with two or fewer vertices.

I believe that the canonical reference for this result is [1], though the proof is somewhat complicated with several cases. There are references to some more streamlined proofs of this result in [2], but I haven't tracked those down.

1. Whitney, Hassler. "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54.1 (1932): 150-168.

2. Hemminger, R. L. "On Whitney's line graph theorem." The American Mathematical Monthly 79.4 (1972): 374-378.

Answer 2

Your problem is equivalent to Graph Isomorphism under polynomial-time reductions, even if you include edge colors.

First, GI is equivalent (under polynomial-time Turing reductions) to computing generators of the automorphism group. From those generators it is easy (using standard permutation group machinery) to compute the edge orbits in polynomial time.

Conversely, if you can determine edge orbits, then to determine if two graphs $G,H$ are isomorphic, you consider their disjoint union $K = G \sqcup H$ and get the edge orbits there. Then $G \cong H$ iff every edge orbit includes at least one edge from $G$ and one from $H$.

(Both directions work with or without colors.)