MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following arose as a side issue in a project on graph reconstruction.

Problem: Let $a(n)$ be the greatest order of the automorphism group of a 3-connected cubic graph with $n$ vertices. Find a good upper bound on $a(n)$.

There is a paper of Opstall and Veliche that finds the maximum over all cubic graphs, but the maximum occurs for graphs very far from being 3-connected.

I foolishly conjecture: for $n\ge 16$, $a(n) < n 2^{n/4}$.

When $n$ is a multiple of 4 there is a vertex-transitive cubic graph achieving half the conjectured bound, so if true the bound is pretty sharp.

The maximum does not always occur for vertex-transitive graphs. There is no vertex-transitive counterexample to the conjecture with less than 1000 vertices.

Any bound for which the exponential part is $2^{cn}$ for $c<\frac12$ is potentially useful.

Added: As verret pointed out in a comment, a paper of Poto─Źnik, Spiga and Verret, together with the computation I mentioned, establishes the conjecture for vertex-transitive graphs, so the remaining problem is whether one can do better for non-transitive graphs. For 20, and all odd multiples of 2 vertices from 18 to at least 998 (but not for 4-16 or 24 vertices) the graph achieving the maximum is not vertex-transitive.

share|cite|improve this question
The family of vertex-transitive graphs you have in mind are in fact best possible among large enough cubic vertex-transitive graphs. (n=100 or so should already suffice.) This is shown in the paper : "Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs", Therefore, a counter-example to your conjecture will necessarily be not vertex-transitive. – verret Jul 17 '13 at 2:54
Great! I vaguely remembered such a paper but hadn't managed to find it today. – Brendan McKay Jul 17 '13 at 3:42
@verret: Any idea what the maximum is for transitive cubic graphs of order an odd multiple of 2? – Brendan McKay Jul 17 '13 at 5:19
In the cubic vertex-transitive case and n twice an odd number, it immediately follows from the same paper that you get a polynomial rather than exponential upper bound. For example Corollary 4 yields that, for large enough n, we have |G|<n^2. This is not best possible, but is not far off, at least for some values of n. If you need more precise estimates, I can show you a few more references that deal with this. (By the way, the link in your "added" section has a typo.) – verret Jul 17 '13 at 13:32

Your Answer


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

Browse other questions tagged or ask your own question.