6
$\begingroup$

I would like a good hint for the following problem that takes into account the position at which I am stuck. The problem is as follows

Let $\mathbb{Z}_n$ be the cyclic group of order $n.$ Find a simple graph $G$ such that $\mathrm{Aut}(G) = \mathbb{Z}_n.$

The book that I am studying suggest that somehow I get rid of the "unwanted" symmetries of the cycle graph $C_n.$ We know that $\mathrm{Aut}(C_n) = D_{2n}$ and somehow we would like to "kill" the "reflections" of $C_n.$ I don't see any way how to "kill" the reflections while "preserving" the rotational symmetries of $C_n.$

Any hint would be appreciated!

  • 0
    No the graphs are simple!2012-12-18

2 Answers 2

7

Make a cycle of repeated units that are not individually symmetric, such as

       *        | [--*---*--]^n     \ /      * 
  • 0
    @Jernej: The figure represents part of the graph you're looking for!2012-12-19
1

To kill the reflection but not the rotation, you can do the following: on the edge $(i,i+1)$ in the $n$-cycle graph, insert two new vertices, say $a_i,b_i$. Create a path of length 1 emanating from $a_i$ and a path of length 2 emanating from $b_i$. The graph now has exactly the following edges for each $i$: $(i,a_i),(a_i,b_i),(b_i,i+1),(a_i,c_i),(b_i,d_i),(d_i,e_i)$.