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?

$\endgroup$
3
  • $\begingroup$ Are your Cayley graphs labelled or directed? $\endgroup$
    – Seirios
    Nov 4, 2012 at 10:04
  • $\begingroup$ They are not directed $\endgroup$
    – Jernej
    Nov 4, 2012 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, 2012 at 18:10

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .