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
    Are the graphs allowed to be directed?2012-12-18
  • 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
    I see your in the "Santa-cap Club"! +1 Happy Holidays!2012-12-18
  • 0
    I think this would be better if you didn't give away an individually symmetric unit, but it's still a clever idea.2012-12-18
  • 0
    Hm.. I don't quite follow your idea! The picture is confusing me. Could you elaborate a bit more? Thanks!2012-12-18
  • 0
    @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.2012-12-18
  • 0
    @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.2012-12-18
  • 0
    What exactly do you mean with unit? A connected component?2012-12-18
  • 0
    @Jernej: I'm not using "unit" in any precise technical sense, but as a conceptual "part" you can somehow, in an appropriate way, build your solution from several copies of.2012-12-18
  • 0
    Hm I still don't see it. Could you elaborate a bit more, please? Thanks!2012-12-19
  • 0
    @Jernej: I have no idea what else I could say. "Take the unit in the figure, repeat it in a cycle $n$ times." There, now I have practically written your solution for you. What is it you don't see?2012-12-19
  • 0
    I don't know what the figure represents2012-12-19
  • 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)$.