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

2 Answers 2

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
2  
@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 yesterday
    
@Bredan, note that here $n$ is the order of the graph. –  verret yesterday
    
@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 yesterday

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

share|improve this answer

Your Answer

 
discard

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.