17
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ 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", arxiv.org/abs/1010.2546. Therefore, a counter-example to your conjecture will necessarily be not vertex-transitive. $\endgroup$
    – verret
    Jul 17, 2013 at 2:54
  • $\begingroup$ Great! I vaguely remembered such a paper but hadn't managed to find it today. $\endgroup$
    – Brendan McKay
    Jul 17, 2013 at 3:42
  • $\begingroup$ @verret: Any idea what the maximum is for transitive cubic graphs of order an odd multiple of 2? $\endgroup$
    – Brendan McKay
    Jul 17, 2013 at 5:19
  • 2
    $\begingroup$ 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.) $\endgroup$
    – verret
    Jul 17, 2013 at 13:32

0

Reset to default

Your Answer

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