5
$\begingroup$

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?

  • 0
    Are your Cayley graphs labelled or directed?2012-11-04
  • 0
    They are not directed2012-11-04
  • 3
    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.2012-11-04

1 Answers 1