Example of a simple graph isomorphic to a permutation group.

Solution 1:

At first I thought a solution wouldn't be too hard to find: simply take the triangle graph and attach various subgraphs to each node. This doesn't work, because it either: doesn't restrict any symmetries, or restricts too many symmetries.

It's apparently not as easy as it sounds to construct graphs with cyclic automorphism groups, but a little googling returned this Mathworld page. Just find the word "cyclic" on the page to see some examples.

Solution 2:

I think the following should be a way to produce a graph $G$ with a cyclic automorphism group.

I first claim that WLOG we may work with colored graphs, i.e. we may give our vertices colors, and ask that our automorphism sends vertices of the same color to one another.

Indeed, given a finite colored graph $G$, call its colors $c_1, \ldots, c_n$, and the maximal degree of any vertex $d \ll D$. We can produce an uncolored graph $\tilde{G}$ by adding for each $c_j$ colored vertex $v$ of $G$ $D^j$ new vertices $v_1, \ldots, v_{D^j}$ each connected to $v$. Replace $v_i$ with a chain of vertices $v \rightarrow \cdot \rightarrow \cdot \ldots \rightarrow \cdot$ of length $i$ so that these new `vertices' will be ordered.

I claim that uncolored automorphisms of $\tilde{G}$ are canonically in bijection with colored automorphisms of $G$. Namely, given a colored automorphism $\gamma$ of $G$, induce an automorphism of $\tilde{G}$ by sending the $i^{th}$ chain emanating from $v$ to the $i^{th}$ chain emanating from $\gamma(v)$.

Given an automorphism of $\tilde{G}$, we recover a colored automorphism of $G$ as follows. By construction, the new vertices of $\tilde{G} \setminus G$ have degree 1 or 2, and old vertices of $G$ of color $c_j$ have degree $\approx D^j$. So any automorphism of $\tilde{G}$ in fact sends $G$ into itself, and preserves colors, by preservation of degree.

These given maps should be inverse maps of sets, and in fact groups, as desired.

It then suffices to exhibit a colored graph with automorphism goup $\mathbb{Z}/n\mathbb{Z}$. Take a colored triangle for each $i \in \mathbb{Z}/n\mathbb{Z}$ and connect it to its neighbors as below:

I claim the evident cyclic permutations are the only automorphisms of this graph. Terminology: let us call the red, blue, and green vertices of triangle $i$ red $i$, blue $i$, green $i$.

Suppose an automorphism $\sigma$ sends blue 0 to blue $i$. Each blue vertex is connected to a unique green vertex, so green 0 goes to green $i$. Similarly, red 1 goes to red $i+1$, etc. as desired.