0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Christian Sievers Jun 18 '16 at 1:25
  • 1
    $\begingroup$ I don't know. I see no problems editing this. $\endgroup$ – Christian Sievers Jun 18 '16 at 1:35
  • 1
    $\begingroup$ As you may know, every finite group can be realized as the automorphism group of a graph. en.wikipedia.org/wiki/Frucht%27s_theorem $\endgroup$ – Gerry Myerson Jun 18 '16 at 2:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jun 18 '16 at 3:03
  • 1
    $\begingroup$ Take an $n$-cycle and then attach something identical to each vertex. $\endgroup$ – Morgan Rodgers Jun 18 '16 at 19:32
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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