# 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.
There is some confusion here between abstract group isomorphism (agi) and permutation group isomorphism (pgi, aka conjugacy in the symmetric group). Not all permutation groups (pgi sense) occur for regular graphs or even for graphs at all. On the other hand, groups agi to $S_n$ occur on regular graphs other than empty or complete (consider the linegraph $L(K_n)$). Also note Gerry's answer, which limits $n$ and $k$. –  Brendan McKay Jan 29 at 23:53
@Bredan, note that here $n$ is the order of the graph. –  verret Jan 30 at 3:43