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?

  • $\begingroup$ Are your Cayley graphs labelled or directed? $\endgroup$ – Seirios Nov 4 '12 at 10:04
  • $\begingroup$ They are not directed $\endgroup$ – Jernej Nov 4 '12 at 10:07
  • 3
    $\begingroup$ The trick is to show that the automorphism group of $\Gamma$ contains a copy of the dihedral group of order $2n$ acting regularly, then apply Sabidussi. To get the copy, note that $\mathrm{Aut}(\Gamma)$ contains a copy of $D_{4n}$ generated by the cyclic subgroup of order $2n$ and the automorphism of order of $\mathbb{Z}_{2n}$ that maps each element of its inverse. So you are left with a group theory problem: show that $D_{4m}$ acting on $2n$ points contains a copy of $D_{2n}$ acting regularly. $\endgroup$ – Chris Godsil Nov 4 '12 at 18:10

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.


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.