Smallest graphs with given automorphism group

Abstract

For a finite group $G$, denote by $\alpha (G)$ the minimum number of vertices of any graph $\Gamma$ having $\text{Aut}(\Gamma )\cong G$. In this paper, we prove that $\alpha (G)\le |G|$, with specified exceptions. The exceptions include four infinite families of groups, and 17 other small groups. Additionally, we compute $\alpha (G)$ for the groups $G$ such that $\alpha (G)>|G|$ where the value $\alpha (G)$ was previously unknown.

arXiv comment27 pages, 1 figure