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

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.

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.

• Nice answer to the first point. This possibly extends to the second point by implying that reducing the problem to vertex automorphisms in the line graph remains a plausible option. The graphs I am considering may actually be disconnected and the orbit of non-edges be concerned by the computation. Do you think the exceptions are still limited in this case, or essentially reduce to the above exceptions in terms of components (or using the complement)? For example, if only the edges $bc$ and $bd$ exist in graph $G$, then non-edges $ab$ and $cd$ will (wrongly) be seen as being on the same orbit. – Arnaud Casteigts Oct 23 '19 at 20:46
• Hm. I'm not 100% sure about disconnected graphs. Certainly, any components that look like any of the 3 exceptional graphs will cause a problem for you. Also, I'm not entirely sure about your treatment of the orbits of "non-edges". Non-edges in the original graph $G$ should not contribute any vertices at all to the line graph $L(G)$. – mhum Oct 23 '19 at 22:40

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

• Could you please elaborate on "(using standard permutation group machinery)". I see how to compute the orbits of the vertices from the generators (this part is OK), but I don't see how to extend that to the orbits of the edges and non-edges. For sure, the non-edges cannot be fully characterized by the pair of orbits of their endpoints, if this was your underlying idea (probably not): consider for instance a $C_6$. All the vertices are on the same orbit, but there are two different orbits for non-edges. – Arnaud Casteigts Oct 23 '19 at 21:00
• Regarding the colors, I was referring to proper coloring, asking essentially if the fact that it is proper may help in some way (e.g. two neighbors vertices/edges cannot be on the same orbit). Does this impact the last sentence of your answer? – Arnaud Casteigts Oct 23 '19 at 21:02
• To all intents and purposes, I found how to compute the edge orbits from the generators (as suggested), this is explained there: computationalcombinatorics.wordpress.com/2012/10/05/…. Thanks! (My question about proper coloring is still open.) – Arnaud Casteigts Oct 25 '19 at 8:55