Realizable automorphism groups of graphs

Question

Frucht's theorem states that every group can be realized as an automorphism group of a graph. I am interested in which subgroups of $S_n$ can be realized as an automorphism group of a graph on $n$ vertices. Are there any things we can say about these groups or their actions which don't tautologically follow from the definition of automorphism groups of graphs?

Answer 1

A graphical regular representation (GRR) of a group $G$ is a Cayley graph $X$ such that $\mathrm{Aut}(X)\cong G$. We know that if $|G| > 32$ and $G$ is neither abelian with exponent greater then two, nor generalized dicyclic, then $G$ has a GRR. A generalized dicyclic group is a non-abelian group that admits an automorphism that maps each element to itself or its inverse; they necessarily have an abelian subgroup of index two. (There is an explicit presentation.)

If $G$ is cyclic with order a prime power $q$ and $G$ acts as a group of automorphisms of a graph $X$, then $G$ must have an orbit of length $q$. f $|V(X)|=q$, then $X$ is a Cayley graph for $G$ and $|\mathrm{Aut}(X)| \ge 2q$. So cyclic groups of prime power order $q$ cannot be realized as automorphism groups of graphs with at most $q$ vertices.

Babai (On the minimum order of graphs with given group https://cms.math.ca/10.4153/CMB-1974-082-9) shows that if $G$ is not cyclic of order 3, 4 or 5, then it is the full automorphism group of a graph with at most $2|G|$ vertices. We can use this to realize more groups as automorphism groups of small graphs. For example if $G$ is cyclic of order 63, take the disjoint union of graphs on 14 and 18 vertices (with automorphism groups cyclic of order 7 and 9 respectively) along with an asymmetric graph on 41 vertices to get a graph on 63 vertices with automorphism group isomorphic to $G$.