# Cubic Cayley (undirected) graphs

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.

• You seem to be distinguishing between graph isomorphism and Cayley graph isomorphism, but it is not clear to me what you mean by the latter. – Chris Godsil Aug 27 '14 at 16:19
• A Cayley graph isomorphism is a graph isomorphism of Cayley graphs which is induced by an isomorphism of the corresponding groups. – Robin Saunders Aug 27 '14 at 16:24

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.

• Both of the answers posted here have been informative, but I'm accepting this one on the basis that verret is "really" responsible for both of them. I hope this is acceptable etiquette. – Robin Saunders Sep 3 '14 at 16:19

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.

• I'm a bit confused about your last paragraph. Clearly, graphs of type A and B are not Cayley isomorphic'', but what is meant by the first sentence? Certainly the same group can give rise to graphs of type A and B, even (graph) isomorphic ones. – verret Aug 27 '14 at 18:50
• @verret, thanks for the correction. I've been sloppy and will correct shortly. In any case, the real point of my answer is that the OP should read your work, so I'm glad you also showed up to answer :-) – Nick Gill Aug 27 '14 at 19:53