Show that a graph is arc-transitive

168 Views Asked by At

$\mathbf{Exercise}$:

Show that a graph $Г = Cay(\mathbb{Z}_{17},\{1,2,4,8,16,15,13,9\})$ is acr transitive if we know that it is vertex transitive.

$\mathbf{My \ soluton:}$

So on our lectures we had a Proposition that states:

If graph is vertex transitive then it is arc transitive $\Longleftrightarrow$ for any $v \in V(Г)$: $Aut(Г)_v$ acts transitively on $Г(v)$ ,where $Г(v)$ represents neighbors of $v$ in a graph.

So i will use this proposition. So after doing some calculations we will find out that $Aut(\mathbb{Z}_{17},\{1,2,4,8,16,15,13,9\})=\{ \phi_1,\phi_2,\phi_4,\phi_8,\phi_9,\phi_{13},\phi_{15}, \phi_{16}\}$.

We also know that $Г(0) = \{1,2,4,8,16,15,13,9\}$. And that $Aut(\mathbb{Z}_{17},\{1,2,4,8,16,15,13,9\}) \leq Aut(Г)_0$.

My question is the following : Since we know that $Aut(\mathbb{Z}_{17},\{1,2,4,8,16,15,13,9\})$ acts transitively on $Г(0) = \{1,2,4,8,16,15,13,9\}$ can we conclude that $Aut(Г)_0$ acts transitively on $Г(0) = \{1,2,4,8,16,15,13,9\}$ knowing that $Aut(\mathbb{Z}_{17},\{1,2,4,8,16,15,13,9\}) \leq Aut(Г)_0$ ?

1

There are 1 best solutions below

0
On

But the graph you specified is two copies of the directed complete graph (w arcs going in both directions), with the elements in the 8-element group $\{2^n; n$ an integer $\}$ forming one copy, and the remaining elements of $\mathbb{Z}/17\mathbb{Z}$ forming the other.

That is your answer right there--vertex-disjoint copies of the directed complete graph w the same number of vertices in each copy is arc-transitive, make sure you can see why.