Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

2 Answers 2

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

       *
       |
[--*---*--]^n
    \ /
     *
share|improve this answer
    
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
show 6 more comments

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.