Cubic Cayley (undirected) graphs

Question

The generators of a cubic Cayley graph always include at least one involution, since 3 is odd. There are then two possibilties for the other two generators: either (A) they are also (distinct) involutions, or (B) they are each other's inverses and of order >2. Note that

• non-isomorphic Cayley graphs can be isomorphic as graphs, so that the same cubic graph may arise as a Cayley graph of both types A and B;
• a single group can have non-isomorphic cubic Cayley graphs, so that the same group may have Cayley graphs of both types A and B;
• in particular, it might even be possible for a single group to give rise to non-isomorphic cubic Cayley graphs which are isomorphic as graphs.

What is known about the characterizations of, or relationship between, the two types A and B of cubic Cayley graphs, and in particular the situations in which they can coincide - either in the sense of being isomorphic as graphs, or of coming from the same group (or possibly both)?

I hope this question is not too vague.

Answer 1

Everything that is not obviously forbidden can happen.

For example, a single group can have two Cayley graphs that are isomorphic (as graphs) but which are not of the same type. Such examples will definitely not be isomorphic as Cayley graphs (in your terminology).

I think if you take the dihedral group $D_4=\langle a,b|a^4,b^2,(ba)^2\rangle$ then $\{a,a^{-1},b\}$ and $\{b,ba,ba^2\}$ yield the smallest example. (They are both isomorphic to the cube.)

Otherwise, your question IS a little vague but part of it is closely related to so-called Cayley isomorphic graphs or CI-graphs. There is a large literature on these, so maybe have a look to see if it helps.

Answer 2

I suggest you refer to this paper:

Cubic vertex-transitive graphs on up to 1280 vertices by Primoz Potocnik, Pablo Spiga and Gabriel Verret.

The paper constructs the graphs in the title and, of course, this includes all of the cubit Cayley graphs with at most 1280 vertices. They give a lot of data about the asymptotics of, for instance, the number of Cayley graphs with $n$ vertices as a proportion of all vertex-transitive graphs with $n$ vertices...

Of particular relevance to your question is their Section 3 where they explain their methodology for constructing those graphs that are Cayley graphs. For instance their (very easy) Lemma 2 states the following:

Lemma 2: Let $G$ be a finite graph and let $\Gamma(G,S)$ be a connected Cayley graph for $G$ of valency at most $3$. Then $G/G'$ is isomorphic to either $C_2$, $C_2\times C_2$, $C_2\times C_2\times C_2$, $C_2\times C_r$ or $C_r$ (where $r>2$).

I write $G'$ for the derived subgroup of $G$. It should be quite clear how the various possibilities may arise (indeed a proper subset will arise when the valency is EXACTLY $3$).

This lemma can be used to restrict possible coincidences of Type A and B: for instance a Cayley graph of type A can coincide with a group $G$ such that $G/G'$ is isomorphic to $C_2\times C_2\times C_2$, but that is not possible for a Cayley graph of type B. Note that, in general, you will not obtain a Cayley graph isomorphism (in the notation of your comment) for graphs of different types.