<p>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. </p>

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

<p>For any vertex-automorphism <span class="math-container">$\pi \in \Gamma_V(G)$</span>, we observe that there is a natural edge-automorphism <span class="math-container">$\pi':E \to E$</span> induced by <span class="math-container">$\pi$</span>. Let <span class="math-container">$\Gamma'_V(G)$</span> denote the group of such induced edge-automorphisms.</p>

<blockquote>
  <p><strong>Theorem</strong>: <span class="math-container">$\Gamma'_V(G)$</span> is isomorphic to <span class="math-container">$\Gamma_E(G)$</span> for all simple, connected <span class="math-container">$G$</span> with three or more vertices, with three exceptions: <span class="math-container">$K_4$</span>, <span class="math-container">$K_4$</span> with one edge deleted, and the graph illustrated above within the question.  </p>
</blockquote>

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

<p>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.</p>

<ol>
<li><p>Whitney, Hassler. "<a href="https://www.jstor.org/stable/2371086" rel="noreferrer">Congruent Graphs and the Connectivity of Graphs</a>." American Journal of Mathematics 54.1 (1932): 150-168.</p></li>
<li><p>Hemminger, R. L. "<a href="https://www.jstor.org/stable/2978089" rel="noreferrer">On Whitney's line graph theorem</a>." The American Mathematical Monthly 79.4 (1972): 374-378.</p></li>
</ol>

CC BY-SA 4.0
2019-10-23T20:46:56.883Z
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
CC BY-SA 4.0
2019-10-23T22:40:51.503Z
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
CC BY-SA 4.0
2019-10-22T18:59:37.877Z
2019-10-22T19:10:12.183Z
2019-10-22T19:10:12.183Z
mhum
<p>Your problem is equivalent to Graph Isomorphism under polynomial-time reductions, even if you include edge colors. </p>

<p>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.</p>

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

<p>(Both directions work with or without colors.)</p>

CC BY-SA 4.0
2019-10-23T21:00:18.610Z
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
CC BY-SA 4.0
2019-10-23T21:02:55.860Z
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
CC BY-SA 4.0
2019-10-25T08:55:34.927Z
To all intents and purposes, I found how to compute the edge orbits from the generators (as suggested), this is explained there: https://computationalcombinatorics.wordpress.com/2012/10/05/computing-orbits-with-nauty/. Thanks! (My question about proper coloring is still open.)
Arnaud Casteigts
CC BY-SA 4.0
2019-10-22T19:33:24.327Z
2019-10-22T19:33:24.327Z
Joshua Grochow
<p>A (vertex) automorphism in a graph <span class="math-container">$G=(V,E)$</span> is a permutation <span class="math-container">$\sigma$</span> of the vertices that preserves adjacency, namely <span class="math-container">$\sigma(u) \sigma(v) \in E$</span> if and only if <span class="math-container">$uv \in E$</span>. The automorphisms of a graph induce a partition of the vertices into <em>orbits</em>, 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 <span class="math-container">$G$</span> below, there are three orbits: <span class="math-container">$\{a\}$</span>, <span class="math-container">$\{b\}$</span>, and <span class="math-container">$\{c,d\}$</span>.</p>
<p><a href="https://i.sstatic.net/u94fz.png" rel="noreferrer"><img src="https://i.sstatic.net/u94fz.png" alt="A graph G and its line graph L(G)" /></a></p>
<p>The present question focuses on the analogue concept for <em>edges</em>. Several definitions of edge automorphisms seem to co-exist, which confuses me. For instance, Wolfram MathWorld
(<a href="http://mathworld.wolfram.com/EdgeAutomorphism.html" rel="noreferrer">link</a>) 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.</p>
<p>What troubles me with this definition is that edges such as <span class="math-container">$ab$</span> and <span class="math-container">$cd$</span> in graph <span class="math-container">$G$</span> 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 <span class="math-container">$L(G)$</span> 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 <em>adjacency-based</em> versus <em>symmetry-based</em>.
Now, my questions:</p>
<ol>
<li><p>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.</p>
</li>
<li><p>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.</p>
<p>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.</p>
</li>
<li><p>(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.</p>
</li>
</ol>

<graph-theory><reductions><graph-colouring><symmetry><automorphism>
Computing the edge orbits of a graph (and discussing definitions)
Arnaud Casteigts
# Computing the edge orbits of a graph (and discussing definitions)

(Asked by: username_0 on 2019-10-20)

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\}$.

[![A graph G and its line graph L(G)](https://i.sstatic.net/u94fz.png)](https://i.sstatic.net/u94fz.png)

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](http://mathworld.wolfram.com/EdgeAutomorphism.html)) 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.

**Tags:** graph-theory, reductions, graph-colouring, symmetry, automorphism


---

## 2 answers

### Answer by username_1 on 2019-10-22. Score: 5 | Accepted answer

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](https://www.jstor.org/stable/2371086)." American Journal of Mathematics 54.1 (1932): 150-168.
2. Hemminger, R. L. "[On Whitney's line graph theorem](https://www.jstor.org/stable/2978089)." The American Mathematical Monthly 79.4 (1972): 374-378.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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)$.  

---

### Answer by username_2 on 2019-10-22. Score: 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.)

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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?  
> **username_0**: To all intents and purposes, I found how to compute the edge orbits from the generators (as suggested), this is explained there: https://computationalcombinatorics.wordpress.com/2012/10/05/computing-orbits-with-nauty/. Thanks! (My question about proper coloring is still open.)  

---

