Largest size of the automorphism group of a 3-regular graph on 12 vertices

Question

Let $ G $ be a 3-regular connected graph on 12 vertices. We also assume that $ G $ is undirected, unweighted, and simple.

What will be the largest possible size of the automorphism group of $ G $?

The example I found with a large automorphism group is a hexagonal prism, whose automorphism group is generated by (1 2 3 4 5 6)(7 8 9 10 11 12), (1 7)(2 8)(3 9)(4 10)(5 11)(6 12), and (2 6)(3 5)(8 12)(9 11), corresponding to a $\pi/6$ - rotation and reflections. This automorphism group has size 24.

Can anyone come up with an example with larger automorphism group?

Answer 1

Yes, there are 3-regular ("cubic") graphs with 12 nodes and more automorphisms, but not many.

It turns out that Wikipedia has a list of simple cubic graphs with up to 12 vertices! And it just so happens to list the size of their automorphism groups.

The list unfortunately does not number various graphs, which makes it hard to refer to them. But the skeleton of the hexagonal prism is indeed there near the end, having 24 automorphisms (and the truncated tetrahedron graph too!).

The most automorphisms appears to be 64, from:

G = Graph({1:[2, 4, 12], 2:[3, 5], 3:[4, 6], 4:[5], 5:[6], 6:[7], 7:[8, 10], 8:[9, 11], 9:[10, 12], 10:[11], 11:[12]}) #64 auto, but sage claims 16
print G.automorphism_group().cardinality(), "automorphisms\n"
G.plot()

Honorable mentions include this nifty-looking one with 48 automorphisms:

G = Graph({1:[2, 11, 12], 2:[3, 12], 3:[4, 5], 4:[5, 6], 5:[6], 6:[7], 7:[8, 9], 8:[9, 10], 9:[10], 10:[11], 11:[12]})
print G.automorphism_group().cardinality(), "automorphisms\n"
G.plot() #48 auto

And the stately Franklin Graph, also with 48 automorphisms (nicer drawing on Wikipedia):

G = graphs.FranklinGraph()
print G.automorphism_group().cardinality(), "automorphisms\n"
G.plot() 

And because I already took a screenshot and wrote out its connections, I'll include this weirdo with 32 automorphisms:

L = [[0,1], [0,6], [0,11], [1,2], [1,4],
[2,3], [2,5], [3,4], [3,6], [4,5],
[5,6], [7,8], [7,9], [7,11], [8,9],
[8,10], [9,10], [10,11]]
G = Graph([tuple(thing) for thing in L]) #32 auto
print G.automorphism_group().cardinality(), "automorphisms\n"
G.plot()

EDIT: As an addendum, it turns out that the LCF notation given in the table is actually quite handy for referring to the graphs. Take the 2nd to last example in the table, listed as having LCF notation $[6, 6, −3, −5, 5, 3]^2$. We can ask Sage to work with such a graph by calling

import networkx
K = networkx.LCF_graph(12, [6, 6, -3, -5, 5, 3], 2)
G = Graph(K)

using the NetworkX documentation for LCF notation here. Unfortunately the − symbol on Wikipedia isn't a symbol that Sage recognizes, so you'll have to replace those with the - symbol your keyboard produces.