# Automorphism group of regular graph

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

-

## 2 Answers

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 '13 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 '13 at 12:39
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 '15 at 23:53
@Bredan, note that here $n$ is the order of the graph. – verret Jan 30 '15 at 3:43
@BrendanMcKay The question seemed to me to be about the abstract group structure of the automorphism group of a regular graph with n vertices. – Olivier Jan 30 '15 at 14:05

There is a theorem of Wormald, a divisibility condition on the order of the group. See http://www.jstor.org/discover/10.2307/2043017?sid=21105736858423&uid=2129&uid=70&uid=4&uid=2&uid=3739256&uid=3739808

-