Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.