# Graphs whose automorphism group is the cyclic group

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!

-
Are the graphs allowed to be directed? – Ben Millwood Dec 18 '12 at 13:51
No the graphs are simple! – Jernej Dec 18 '12 at 14:25

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

       *
|
[--*---*--]^n
\ /
*

-
I see your in the "Santa-cap Club"! +1 Happy Holidays! – amWhy Dec 18 '12 at 14:53
I think this would be better if you didn't give away an individually symmetric unit, but it's still a clever idea. – Ben Millwood Dec 18 '12 at 15:03
Hm.. I don't quite follow your idea! The picture is confusing me. Could you elaborate a bit more? Thanks! – Jernej Dec 18 '12 at 15:09
@BenMillwood: I tried but failed to find a way to describe the idea without giving a concrete solution away, while still saying something more than the vague hint the OP already had from his book. – Henning Makholm Dec 18 '12 at 15:09
@Jernej: The diagram show one non-symmetric unit -- there's no automorphism that reverses it, because the degree-1 vertex connects to the right and not to the left. – Henning Makholm Dec 18 '12 at 15:26

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)$.

-