# Graph Automorphisms

This post is concerning automorphisms of graphs, which quantify the symmetry existing within the graph structure. Given two graphs $G$ and $H$, a bijection $f:V(G)\to V(H)$ which maintains adjacency, i.e. $xy\in E(G)\Leftrightarrow f(x)f(y)\in E(H)$, is called an isomorphism and the graphs $G$ and $H$ are called isomorphic. Clearly isomorphic graphs are essentially the same, with the superficial difference between them on account of different notation used in defining the vertex set. A isomorphism from the graph $G$ to itself is called an automorphism. It is easy to see that the set of all automorphisms on a graph $G$ together with the operation of composition of functions forms a group. This group is called the automorphism group of the graph, and is denoted by $A(G)$.

In the remainder of this post we investigate some well known graphs and find out their automorphism groups.

The first graph we take up is the complete graph $K_n$. Any permutation of its $n$ vertices is in fact an automorphism for adjacency is never lost. Its automorphism group is therefore $S_n$.

The next graph is the complete bipartite graph $K_{m,n}$. First consider the case $m\not= n$. The $m$ vertices in the first partite set can be permuted in $m!$ ways and similarly $n!$ ways for the second partite set. Corresponding to each of these $m!n!$ limited permutations we get automorphisms because adjacency is never disturbed. On the other hand, no automorphism can result from swapping a vertex from the first partite set and the second partite set because unless such a swap is done in its entirety (i.e. all the vertices from the first partite set swap places with the vertices in the second partite set), adjacency will be lost. A swap can be done in entirety only if $m=n$ which is not the case we are considering. Hence no further automorphisms can result. Moreover by the multiplication rule it is simple to observe that the automorphism group would be isomorphic to $S_m\times S_n$.

In the case of $m=n$, we first pair off the vertices in the two partite sets against each other. This is also an automorphism, say $f$. Now for each of the $m!m!$ ways of permuting vertices within partite sets, an additional automorphism arises. It is obtained in this fashion: After permuting the vertices within the partite sets by the particular way we swap each vertex with its pair in the other partite set. Clearly this yields $2m!m!$ automorphisms and furthermore no more are possible. Since every element of $A(K_{m,m})$ can be written as a unique product of an automorphism collection of the type covered in counting the first $m!^2$ ways (which is not hard to see is a normal subgroup, being of index 2) and of the subgroup $\{Id,f\}$ so we see that the automorphism group is $S_m\times S_m\rtimes \mathbb{Z}_2$.

The next graph we take up is the cycle graph $C_n$. Firstly note that any automorphism can be obtained in this way: A given vertex $v$ may be mapped to any of the $n$ vertices available (including itself). As soon as that is done, an adjacent vertex to $v$ has only two choices left: it can either be in the counter clockwise direction to $v$ or in the clockwise direction to $v$. Once that choice is also made, no other choices are required. Hence we get $2n$ automorphisms this way and there can be no others. Also, it is clear that two kinds of automorphisms suffice to generate this group: rotation, and swapping the notion of clockwise and counter clockwise (assuming we draw the cycle graph as equally spaced points on the unit circle; there is no loss of generality in doing that). But both these automorphisms also generate the dihedral group $D_n$ which also has $2n$ elements. It follows that $A(C_n)=D_n$.

The final graph we take up is the well known Petersen graph. Instead of directly considering what possible functions are there in its automorphism group (although such an approach is possible) we approach the problem through the concept of line graphs.

Definition: A line graph $L(G)$ of a graph $G$ is the graph whose vertices are in one to one correspondence with the edges of $G$, two vertices of $L(G)$ being adjacent if and only if the corresponding edges of $G$ are adjacent.

Lemma 1: $L(K_5)$ is the complement of the Petersen graph.
Proof: It is clear that if the vertices of $K_5$ are labelled $1,2,\ldots,5$ then its 10 edges are the ${5 \choose 2}$ 2-subsets of $\{1,\cdots,5\}$. The line graph $L(K_5)$ thus has 10 vertices, labeled by these 10 2-subsets $\{i,j\}$. Two vertices $\{i,j\}, \{k,\ell\}$ are adjacent in $L(K_5)$ iff the two 2-subsets have a nontrivial overlap. The complement of $L(K_5)$ is the graph with the same 10 vertices, and with two vertices being adjacent iff the corresponding two 2-subsets are disjoint. But this is the very definition of the Petersen graph.$\Box$

Lemma 2: $A(G)$ is equal to $A(\bar{G})$.
Proof: If $\sigma\in A(G)$ then for any two vertices $x,y$ we have $xy\in E(G)\Leftrightarrow \sigma(x)\sigma(y)\in E(G)$, i.e. $xy\not\in E(G)\Leftrightarrow \sigma(x)\sigma(y)\not\in E(G)$, i.e. $xy\in E(\bar{G})\Leftrightarrow \sigma(x)\sigma(y)\in E(\bar{G})$ so that $\sigma\in A(\bar{G})$. The reverse implication follows by replacing $G$ by $\bar{G}$. $\Box$

Theorem 3: The automorphism group of the Petersen graph is $S_5$.
Proof: In view of Lemma 1 and 2 it suffices to find out $A(L(K_5))$ for the automorphism group of the Petersen graph is going to be the same. We let $K_5$ have the vertex set $\{1,\cdots,5\}$ in the sequel.

Take any automorphism $f$ of $K_5$. If we have two edges $ab,cd\in K_5$ with $f(a)f(b)=f(c)f(d)$, then either of two cases arise. Either $f(a)=f(c)$ or not. If $f(a)=f(c)$ then obviously $f(b)=f(d)$ and so by injectivity of $f$ we have $ab=cd$. If $f(a)\not=f(c)$ then it must be that $f(a)=f(d)$. This means that $f(b)=f(c)$ and again by injectivity we have $ab=cd$. What this means is that the function induced by $f$ on $E(K_5)$ in the natural way is injective. It is also surjective as for any $xy\in E(K_5)$ clearly $f\{f^{-1}xf^{-1}y\}=xy$. Finally, this function is an automorphism since $\{xy,xz\}\in E(L(K_5))$ clearly implies and is implied by $\{f(x)f(y),f(x)f(z)\}\in E(L(K_5))$ as there is a common vertex. As our definition of the induced function is obtained in a definite way we have shown that every automorphism of $K_5$ induces a unique automorphism of $L(K_5)$. Moreover, it is easy to see that if $f_1,f_2$ are two automorphisms then the automorphism induced by $f_1\circ f_2$ is the same as the automorphism induced by $f_1$ composed by $f_2$.

We now show that given an automorphism of $L(K_5)$ we can obtain an automorphism of $K_5$ which induces it in the natural way. Let $\pi\in A(L(K_5))$. It is easy to see that the 4-cliques of $L(K_5)$ originate from the stars $K_{1,4}$ of $K_5$. So $L(K_5)$ has exactly $5$ 4-cliques, say $C_1,\cdots ,C_5$ where $C_i$ contains 4 vertices corresponding to the 4 edges in $K_5$ that are incident to a vertex $i$ in $K_5$. Since $\pi$ is an automorphism it sends 4-cliques to 4-cliques. Also, $\pi$ must send two different 4-cliques $C_i,C_j$ with $i\ne j$ to different 4-cliques, because if it sends them to the same 4-clique then a collection of at least 5 vertices is mapped to a collection of $4$ vertices, a contradiction to the injectivity of $\pi$. So $\pi$ induces a permutation of the $C_i$‘s.

Now suppose $\pi$ and $\pi'$ are two different automorphisms in $A(L(K_5))$. Then they differ on at least vertex in $L(K_5)$, say on the vertex $ij\in E(K_5)$. Now given any vertex $xy$ in $L(K_5)$ consider the intersection of the 4-cliques $C_x$ and $C_y$. If $pq$ is some vertex in $C_x\cap C_y$ then $pq$ as an edge in $K_5$ is part of stars with centers $x$ and $y$, i.e. $pq=xy$. Hence the intersection contains only the vertex $xy$. Every vertex of $L(K_5)$ arises in this way. So if $\pi(ij)\ne \pi'(ij)$, then either $\pi (C_i)\ne \pi'(C_i)$ or $\pi(C_j)\ne \pi'(C_j)$ for otherwise $\pi (C_i\cap C_j)=\pi'(C_i\cap C_j)$.

Hence every automorphism of $L(K_5)$ induces a unique permutation of the $C_i$‘s. Moreover distinct automorphisms induce distinct permutations so that the automorphisms and the permutations can be put in one-one correspondence. Consider an automorphism $f$ of the vertices of $K_5$ where $f(i)=j$ if $C_i\to C_j$ in the permutation corresponding to $\pi$. Now a vertex $\{x,y\}\in E(K_5)$ of $L(K_5)$. This is also the intersection of the 4-cliques $C_x$ and $C_y$ and so $\pi(\{x,y\})=\pi(C_x\cap C_y)=\pi(C_x)\cap\pi (C_y)=C_{f(x)}\cap C_{f(y)}=f(x)f(y)$. This shows that $f$ induces $\pi$ as an automorphism.

Hence we have shown that $A(K_5)\equiv A(L(K_5))$. So the Petersen graph has the automorphism group $S_5$. $\Box$