An example of a simple graph whose automorphism group is isomorphic to the cyclic group on 4 elements.

Question

I am looking for an example of a graph whose automorphism group is isomorphic to the cyclic group of order 4. I would most like an example of such a graph with the fewest number of vertices possible.

I wrote a code in Mathematica which says there are not any such graphs with 7 or fewer vertices. I saw an example in another question of such a graph with 12 vertices. Is there such a graph with fewer than 12 vertices?

Answer 1

10 vertices:

In this drawing, the vertices are colored according to their degree.

The red square must be preserved by any automorphism, and its orientation is fixed because each red vertex is part of exactly one red-green-blue triangle whose green member points towards the next red node.

---

Less than 10 vertices won't do:

Suppose the graph has an automorphism $\sigma$ of order $4$. Then the orbit of each vertex under $\sigma$ has $1$, $2$ or $4$ elements, and there has to be at least one orbit of size $4$ because otherwise $\sigma^2$ would be the identity.

If there is exactly one orbit of size $4$, then $\sigma^2$ swaps exactly two pairs of vertices, and swapping just one of those pairs will necessarily be an automorphism too, so the automorphism group is not $\langle \sigma\rangle$.

Now suppose there are exactly two orbit of size $4$ and every other orbit (if any) has size $1$. Consider how many vertices in orbit A each vertex in orbit B is connected to:

• If $0$ or $4$, then the two orbits can be rotated independently of each other, and the automorphism group is not $\langle \sigma \rangle$.
• If $1$ or $3$, then draw orbits A and B in concentric circles such that each vertex is right outside the vertex in the other orbit it is (or isn't, in case $3$) connected to. This drawing has enough symmetry that the automorphism group is at least $D_8$.
• If $2$, and the two vertices a node is connected to are opposite each other, then turning one of the orbits through $180^\circ$ while leaving the other alone will be an automorphism, and the automorphism group is not $\langle\sigma\rangle$.
• If $2$, and the two vertices a node is connected to are neightbors, then draw orbits A and B in concentinc circles such each vertex is in the middle of the two vertices it is connected to. Again, this drawing has enough symmetry that the automorphism group is at least $D_8$.

Therefore, if our graph has symmetry group $C_4$, then there will at least two orbits of size $4$ and at least one additional orbit of size either $2$ or $4$. That accounts for at least $10$ vertices in total.

---

A similar argument shows that the smallest graph whose automorphism group is $C_3$ or $C_5$ has $9$ or $15$ vertices, respectively. This means that the sequence of minimal sizes of graphs with automorphism group $C_n$ is $$ 2, 9, 10, 15, \ldots $$ which is enough to find the sequence as A058890 in OEIS; see this for further references and a (complex) general formula.