# Non-trivial graph automorphism groups with $D_n$ as subgroup

I understand that the automorphism group of an $n$ cycle graph is the dihedral group $D_n$ of order $2 n$. From the comment of @Christian, I also understand that $S_n$ is the automorphism group of the complete graph $K_n$ which has $D_n$.

Other than these two obvious cases, I would like to know what are the other known automorphism groups of graphs which have $D_n$ as a subgroup. Of course, the easiest are the graphs which have multiple $n$ cycle graphs as subgraphs or multiple $K_n$ as subgraphs. But, are there other graphs?

• The complete graph with $n$ vertices has the full symmetric group $S_n$ as its automorphism group, which of course has $D_n$ as subgroup. – Christian Sievers Jun 18 '16 at 1:25
• I don't know. I see no problems editing this. – Christian Sievers Jun 18 '16 at 1:35
• As you may know, every finite group can be realized as the automorphism group of a graph. en.wikipedia.org/wiki/Frucht%27s_theorem – Gerry Myerson Jun 18 '16 at 2:53
• Pick any group $G$ that has a subgroup isomorphic to $D_8$ (for example, $C_2\times D_8$, where $C_2$ is cyclic of order 2), use the proof of Frucht to construct as many graphs as you like that have $G$ as automorphism group. – Gerry Myerson Jun 18 '16 at 3:03
• Take an $n$-cycle and then attach something identical to each vertex. – Morgan Rodgers Jun 18 '16 at 19:32

## 1 Answer

One can define various structures such as graphs of valency $k$ (for some fixed $k \ge 3$), bipartite graphs, strongly regular graphs, $k$-chromatic graphs (for fixed $k \ge 2$), or $k$-connected graphs (fixed $k \ge 1$). A structure $\mathcal{C}$ is said to be universal if every finite group is the automorphism group of some graph in $\mathcal{C}$. Each of the structures just mentioned is known to be universal - this means that there exists at least one graph in each of these structures whose automorphism group is isomorphic to the dihedral group $D_n$ of order $2n$.

You can also consider Cayley graphs of the group $D_n$. The automorphism group of a Cayley graph of $D_n$ contains a subgroup isomorphic to $D_n$.

• Could you point me to any reference for what you said about universal structures? – Omar Shehab Jun 21 '16 at 20:52
• "Automorphisms of graphs" by Peter Cameron and the references therein. A preprint version of this chapter survey is available online for download. – Ashwin Ganesan Jun 22 '16 at 3:16