2
$\begingroup$

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

$\endgroup$

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Frucht's construction does not produce regular graphs. There are later variants of the result that do. But your first sentence says it all. $\endgroup$ Mar 15, 2013 at 11:43
  • 2
    $\begingroup$ @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? $\endgroup$
    – Olivier
    Mar 15, 2013 at 12:39
  • $\begingroup$ 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$. $\endgroup$ Jan 29, 2015 at 23:53
  • $\begingroup$ @Bredan, note that here $n$ is the order of the graph. $\endgroup$
    – verret
    Jan 30, 2015 at 3:43
  • $\begingroup$ @BrendanMcKay The question seemed to me to be about the abstract group structure of the automorphism group of a regular graph with n vertices. $\endgroup$
    – Olivier
    Jan 30, 2015 at 14:05
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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