3
$\begingroup$

I know that you can find the size of an automorphism group of a simple graph $G$ by using the Orbit-Stabiliser theorem as follows: let $\DeclareMathOperator{Aut}{Aut}A = \Aut(G)$, and $v$ be a vertex of $G$, where $Av$ denotes the orbit of $v$, and $A_v$ is the stabiliser of $v$, then $|A| = |Av||A_v|$. You can find the orbit of a vertex $v$, then fix it, and consider the orbit of another vertex $w$ when $v$ is fixed, e.g. $B = A_v, |A| = |Av||Bw||B_w|$ et cetera, until all non-trivial orbits and stabilisers have been found.

With that being said, I'm not entirely sure how to apply this method to $L(K_4)$, where $L(G)$ denotes the line graph of a simple graph $G$. This is a 4-regular graph of order 6 - so does any vertex have an orbit of size 6, since each vertex has the same degree? Or does its orbit vary and have something to do with its neighbouring vertices? How can we find the orbit of a vertex by inspection?

$\endgroup$
3
$\begingroup$

Does any vertex have an orbit of size 6, since each vertex has the same degree?

There is indeed only one vertex orbit, containing all six orbits of $L(K_4)$. However in general vertices having the same degree is not sufficient for them to be in the same orbit under automorphisms. For example suppose you add a leaf node to the path graph $P_5$ incident at one of the two noncentral nonleaf nodes; this will leave two vertices of degree two which are obviously not in similar positions in the graph. Of course two vertices having the same degree is a necessary condition.

View $K_4$'s vertex set as $\{1,2,3,4\}$, in which case two vertices $ij$ and $k\ell$ of $L(K_4)$ are adjacent if and only if the sets $\{i,j\},\{k,\ell\}$ contain a common term, e.g. $12$ and $23$ are incident. Since permutations of $\{1,2,3,4\}$ induce automorphisms of $K_4$, they also induce automorphisms of $L(K_4)$, and it's easy to see there is a permutation turning $ij$ into $k\ell$ for any $i,j,k,\ell$. This means the action is "transitive" (it's possible to transition from any vertex to any other vertex via an automorphism) so there's only one orbit.

Some authors may summarize this argument simply declaring there is one orbit "by symmetry."

Note that while we know permutations of $\{1,2,3,4\}$ induce automorphisms of $L(K_4)$, we don't a priori know whether or not there are more automorphisms of $L(K_4)$ than just these kinds.

Pick any vertex, say $12$. Note $34$ is not incident to it, but all four other vertices are. Therefore the stabilizer $A_{12}$ must also stabilize $34$. (Why?) This leaves four vertices $13,14,23,24$ for any other automorphism (in the stabilizer) to permute. Can you check the orbit of $13$ (under the action of $A_{12}$ not $A$) includes $14,24,24$ using permutations of $\{1,2,3,4\}$ which fix $12$? (Note these permutations can swap $1$ and $2$.)

Now pick one of these four vertices, say $13$. What is the stabilizer $(A_{12})_{13}$? Argue any element of it must fix not only $12,13$ but also $34,24$, leaving only $14,23$ to be permuted. Note they can be permuted, since all four other vertices besides $14,23$ are connected to both of them, so it is possible to swap these two vertices and drag the edges along with and that's a valid graph automorphism.

In conclusion, $|A|=6\cdot4\cdot2=48$.


Here is a geometric interpretation. The $K_4$ graph can be interpreted as a tetrahedron, whose full symmetry group $T_h$ has $12$ rotations (two $120^{\circ}$ rotations for each of the four faces, a $180^{\circ}$ rotation for each of the three opposite pairs of edges, and the trivial element) and $12$ reflections (one for each diagonal line on a face), corresponding to even and odd permutations of the four vertices (respectively). We can say $T\cong A_4$ and $T_h\cong S_4$. Moreover, every symmetry of the tetrahedron induces an automorphism of the graph, and $T_h\to\mathrm{Aut}(K_4)$ is an isomorphism.

If one connects the midpoints of the edges of the tetrahedron according to which edges share an endpoint, one gets the line graph $L(K_4)$ represented by an inscribed octahedron. The octahedron's faces may be partitioned into two alternating subsets, four corresponding to the tetrahedron's vertices and four corresponding to the tetrahedron's.

a enter image description here

Note that the dual tetrahedron flips around the original's vertices and faces. That is, if one connects the midpoints of the faces of the tetrahedron according to which faces share an edge one gets a dual tetrahedron. If one rescales the dual tetrahedron until it's the same size as the original, their overlap will be the inscribed octahedron and their convex hull a cube (every cube has a dual pair of inscribed tetrahedra). The octahedron and the cube share the same full symmetry group $O_h$ in which $T_h$ is an index $2$ subgroup. If one applies one of the reflections in $O_h\setminus T_h$ it swaps the two tetrahedra but preserves the octahedron, corresponding to automorphisms of $L(K_4)$ that does not come from an automorphism of $K_4$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for your explanation! I'm surprised to learn that $|A| \neq 4!$, since I know that $\mathrm{Aut}(G) \cong \mathrm{Aut}(L(G))$, when $G$ has at least five vertices and is a simple graph. Is $K_4$ an exception, or are there other graphs like that? $\endgroup$ – remana May 29 at 2:27
  • $\begingroup$ It's evidently an exception. I wasn't even aware of the fact you stated for graphs of more than four vertices, so I don't know of other exceptions. There are only so many graphs of at most four vertices up to isomorphism though, so you could just check them all by hand. $\endgroup$ – runway44 May 29 at 6:25
3
$\begingroup$

Let's start with this:

Does any vertex have an orbit of size 6, since each vertex has the same degree?

The direct answer to this is no. Just because all vertices of a graph have the same degree it does not mean the automophisms act transitively on the vertices. For example, imagine the disjoint union of a $3$-cycle and $4$-cycle. All vertices have degree $2$ but no vertex of the $3$-cycle can be mapped via an isomorphism to a vertex of the $4$-cycle. However, for $L(K_4)$, the automorphism does act transitively for another reason which we'll see in a moment.

Or does its orbit vary and have something to do with its neighbouring vertices? How can we find the orbit of a vertex by inspection?

Perhaphs the most intuitive way to think about some symmetries of $L(K_4)$ is to start with symmetries of $K_4$. We know that you can permute the vertices however you like in $K_4$ and obtain an isomorphism. So let's take any isomophism of $K_4$ and see what it does to the edges. If $a,b \in V(K_4)$ and $\sigma \in Aut(K_4)$ then $\sigma(\{a,b\}) = \{\sigma(a), \sigma(b) \}$. It's easy to check that $\sigma$ is an isomorphism of $L(K_4)$. Furthermore it's also not too hard to show that if $\{a,b \}, \{c,d \} \in E(K_4)$ then there exists an isomorphism $\sigma \in Aut(K_4)$ such that $\sigma(\{a,b \}) = \{c,d \}$. This proves that the action of $A$ on $L(K_4)$ is transitive.

So that's the first step, we have calculated the size of the orbit $|Orb_{A}(v)| = 6$. Let's consider the stabiliser $Stab_{A}(v)$ and I'll give a few hints about how to proceed. We know that any automorphism of $L(K_4)$ that fixes a vertex $v$ sends each neighbour of $v$ to another neighbour of $v$. So let $w$ be a neighbour of $v$, where can $w$ be sent by automorphisms that fix $v$? Hint: it turns out $w$ can be sent to any other neighbour of $v$.

The final step is to think about the automorphisms that fix two neighbouring vertices $v$ and $w$. Such an automohpism must also fix the non-neighbour of $v$ and the non-neighbour of $w$. So the automophism can only permute the two remaining vertices. I'll leave you to check whether or not swapping these vertices is an automophism.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks so much for your answer! I found it very well constructed. Out of curiosity, how would you find the orbit of a vertex if there wasn't a transitive action on a graph? Would you just find the maximum size of an action? $\endgroup$ – remana May 29 at 2:24
  • $\begingroup$ I think this is a hard question in general. You can note that a vertex must be sent to another vertex with the same degree. And then of these vertices you could find explicit automorphisms to check if they are possible. Finding an automophism of a graph is NP-hard: en.wikipedia.org/wiki/… so unless your graph has some extra structure, like a Cayley Graph, then I wouldn't expect that finding orbits of vertices is easy. $\endgroup$ – Oliver Clarke May 29 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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