Cayley graphs on small Dihedral and Cyclic group

Consider the following problem

Let $n \leq 5$ and let $\Gamma = \mathrm{Cay}(C_{2n},S)$ be the
Cayley graph with Cayley set $S$. Show that $\Gamma$ is isomorphic to
$\mathrm{Cay}(D_{2n},S’)$ for a suitable $S’.$

Recall that $\Gamma = \mathrm{Cay}(G,S)$ is a Cayley graph with vertex set $G$ if $G$ is a group, $S$ is a subset of $G\setminus\{e\}$ closed for taking inverses and two vertices $u,v \in G$ are adjacent iff $uv^{-1} \in S.$

It is not very hard to solve the above problem by bruteforcing. The case when $n = 1$ is trivial. For the other cases we observe for example that if $|S| = 1$ then $\Gamma$ is a disjoint union of $K_2$ and similarly if $|S| = |G|-1$ then $\Gamma$ is the complete graph.

One is then left to consider specific values of $|S|$ to deduce that the stated problem is indeed true for $n \leq 5.$

What I was wondering is if there is any other, shorter, way to prove this exercise perhaps employing some properties of small groups and Sabidussi’s Theorem?

Solutions Collecting From Web of "Cayley graphs on small Dihedral and Cyclic group"

This is an attempt to turn Chris Godsil’s argument into an answer. Hopefully someone can check it is also correct. I am a bit suspicious about the proof especially since I never use the fact that $n \leq 5.$

In the proof we will use the following two facts

  • Fact 1. (Sabidussi) $\Gamma$ is a Cayley graph $\rm{Cay}(G,S)$ if and only if $\rm{Aut}(\Gamma)$ contains a subgroup isomorphic to $G$ that acts regularly on $V(\Gamma).$

  • Fact 2. A subgroup $G \leq \rm{Sym}(\Omega)$ is regular if and only if it is transitive and $|G| = |\Omega|.$

Let $\Gamma = \rm{Cay}(C_{2n},S)$ where $\langle g \rangle = C_{2n}.$ Now the maps $r,s:C_{2n} \mapsto C_{2n}$ defined by the rules $$ r(x) = g^2 x$$ and $$s(x) = x^{-1}$$ are clearly automorphisms of $\Gamma$ and hence $H = \langle r,s \rangle \leq \rm{Aut}(\Gamma).$ Moreover $H$ is isomorphic to the dihedral group of order $2n.$ $H$ acts transitively on $V(G)$ and is hence regular on $V(\Gamma)$ by Fact 2. So by Sabidussi’s Theorem $\Gamma$ is isomorphic to $\rm{Cay}(H,S)$ which proves the stated claim.