# Automorphism group of regular graph

Suppose $\Gamma$ is a $k$-regular graph with $n$-vertex. What is the group structure of Automorphism of $\Gamma$?

-

Under these weak hypotheses, the answer is: it could be anything. The trivial group is possible, as well as $\mathfrak S_{n}$ and essentially any group in between by Frucht's theorem (which realizes any group as the automorphism group of a regular graph). Of course, there are trivial obstructions on $k$ and $n$ for some groups to appear (for instance $\mathfrak S_{n}$ of course appears only if $k=0$ or $k=n-1$) but I don't see we can say much more beyond trivialities in the generality you are considering.

-
Frucht's construction does not produce regular graphs. There are later variants of the result that do. But your first sentence says it all. –  Chris Godsil Mar 15 at 11:43
@Chris Godsil Frucht's original construction does not produce regular graphs but the first regular construction is also due to Frucht as far as I know (Graphs of degree three with a given abstract group 1949) so might reasonably be called Frucht's theorem as well. Do you disagree? –  Olivier Mar 15 at 12:39