For which $k$ can a vertex-transitive graph on $n$ vertices have $k\cdot n$ automorphisms?

Question

Given a vertex-transitive graph $G$ on $n$ vertices, the number of automorphisms of $G$ will be $k\cdot n$, where $k$ is the number of automorphisms fixing a given vertex. I have examples for the following $k$:

• $k=1$: The path of length 1, the graph of the snub cube, the Cayley graph associated to any graphical regular representation (GRR) as described here.

• $k=2$: All nontrivial cycles, many other graphs (e.g. the Holt graph)

• $k=3$: The cubic symmetric graphs $F_{26}A, F_{38}A, F_{42}A, F_{56}A, F_{62}A, F_{74}A, F_{78}A, F_{86}A$, probably many more such.

• $k=4$: The Franklin graph, the $12$-circulant graph $(2,3,6)$.

• $k=2m$ for $m\ge3$: The graph of the uniform tiling with $m$ triangles meeting at a vertex, which for $m=3,4,5$ are Platonic solids, for $m=6$ is the standard tiling of the Euclidean plane by triangles, and for $m\ge7$ is an infinite hyperbolic tiling.

I do not know of any graphs which obtain odd $k$ greater than $3$, but I suspect such graphs exist; examples are welcomed, especially a general construction yielding all odd $k$. (I would also be interested to see a construction for $k=2m$ using finite rather than infinite graphs.)

Answer 1

If we take two disjoint copies of any $m$-vertex $k=1$ example, we get an example with $k=m$. (Take the complement, if you'd like a connected graph.) This seems to get examples for many values of $k$ via the GRR construction.

To start off with, Theorem 2 in this paper says that every dihedral group except for $D_3, D_4, D_5$ has a GRR. This gives us every even $k \ge 12$, and the examples in the question give the other even $k$. So it's odd $k$ that we need to worry about.

The paper "GRRs for nonsolvable groups" by Chris Godsil, which I can't find online but is presumably accurately summarized by this MSE post, tells us that we can get a GRR for all groups of order $\ge 32$ except for two cases:

• abelian groups of exponent $\ge 2$, and
• generalized dicyclic groups, defined for example here, which all have even order anyway.

A nonabelian group of order $k$ exists iff $k$ is divisible by either $p^3$ for some prime $p$, or else by $p^iq$ for some primes $p,q$ where $p^i \equiv 1 \pmod q$. (In the first case, we add on some cyclic factors to the nonabelian group $C_p^2 \rtimes C_p$; in the second, to the nonabelian group $C_p^i \rtimes C_q$, where the modular condition is necessary for a nontrivial semidirect product to exist.)

This gives us a construction for all the odd numbers $>32$ in this OEIS sequence, including for example all odd multiples of $21$ (taking $(C_7 \rtimes C_3) \times C_m$ for any odd $m$). There are gaps in some awkward cases: notably, any prime $k$.

---

For an easier finite $k=4m$ example, take two disjoint copies of $C_m$.

Mathematica found me a few explicit examples of graphs with odd $k$ in its database: the graphs it calls

{"DifferenceSetIncidence", {19, 9, 4}}, 
{"DifferenceSetIncidence", {23, 11, 5}}, 
{"DifferenceSetIncidence", {37, 9, 2}}, 
{"DifferenceSetIncidence", {47, 23, 11}}, 
{"Hadamard", {20, 1}}, 
{"Hadamard", {24, 36}}

have $k$ values of $9, 11, 9, 23, 171, 253$, respectively. Also, Mathematica's {"RegularNonplanarDiameter", {6, 3, 111}} is a $111$-vertex graph with $k=3$, so two disjoint copies of this graph give us a $222$-vertex graph with $k=999$.