Gordon Royle's 21-vertex 21-automorphism graph

Question

OEIS A080803 lists the minimal number of vertices $a(n)$ needed to support an undirected graph whose automorphism group has order $n$. The MathWorld page on graph automorphisms links to this sequence and reproduces the list, but there is a discrepancy: MathWorld gives 23 vertices for 21 automorphisms, OEIS gives 21.

The smaller, latter value is explained by Jens Voß:

The value $\text{A080803}(21)=21$ is due to Gordon Royle, who found a graph with 21 vertices whose automorphism group is non-Abelian of order 21 (a 2'-Hall subgroup of the group $\text{PSL}_2(7)$).

No reference is provided for this though.

How exactly does Royle's 21-vertex 21-automorphism graph look like?

There is only one non-abelian group of order 21, $\mathbb Z_7\rtimes\mathbb Z_3$, one of whose Cayley graphs is shown below (taken from Wedd's List):

As a directed graph, this indeed has 21 automorphisms. However, removing the edge orientations allows reflecting the graph, raising the automorphism count to 42. So what was the graph Royle found?

Answer 1

A brute force search reveals that the smallest valency of an example is $8$. (I'm assuming the graph is vertex-transitive.)

Here is an example. Let $a$ be an element of order $3$ in the group, and $b$ and element of order $7$. Then take $S=\{a^2b^2,a^2,a^2b^3,b^4\}$ and then take the Cayley graph with respect to $S\cup S^{-1}$.

Answer 2

The graph Royle found, which I will call the 21-21 graph for its order and automorphism count, can be constructed via the Cayley graph approach outlined in the other answer as follows:

• The vertex set is $\{(a,b):0\le a<3,0\le b<7\}$.
• One-seventh of the edge set $E(n)$ is the union of the following three sets, where the second indices of each vertex are taken modulo 7: $$\{((0,n),v):v\in\{(1,n),(0,n+3),(1,n-3),(1,n-1)\}\}\\ \{((1,n),v):v\in\{(2,n),(1,n+1),(2,n+1),(2,n-2)\}\}\\ \{((2,n),v):v\in\{(0,n),(2,n+2),(0,n+2),(0,n+3)\}\}$$ The entire edge set is then the union of the $E(n)$ for $0\le n<7$.

This creates an 8-regular graph with 84 edges which can split into four 21-edge circuits, one of which is a Hamiltonian cycle. The graph6 code for this graph is TyTXPSjxOI_jfI_IoDWfIC@VoDWCxVC@S]?j.

SageMath code confirming that this graph has 21 automorphisms, as well as SVG sources for the above images, can be found here.