3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you consider graph as oriented? Or you view them as a (reflexive?) incidence relation? Do you allow selfloops/multi-edges? In addition, you probably require that the action on the $n$ vertices is the given original permutation action. The answer to the question "Which subgroups of $S_n$ are equal to the automorphism group of a graph structure on $\{1,\dots,n\}$ is highly sensitive to these details. $\endgroup$ – YCor Jun 24 '18 at 6:53
  • $\begingroup$ Now as regards the question, does it mean anything else than "what can we say that is non-trivial"? I think you could include some context, and possibly some trivial examples. In this kind of question, there can be somewhat trivial observations, and when thinking about such a question I like to have other preoccupations than "is this thing considered as trivial by the OP". In any case, if you think a little about your own problem, you can end up with some more precise and well-thought question. $\endgroup$ – YCor Jun 24 '18 at 6:56
3
$\begingroup$

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

$\endgroup$

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.