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
    Commented 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
    Commented 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
    Commented 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
    Commented Jul 17, 2013 at 13:32

0

Reset to default

You must log in to answer this question.