If we have a regular map, there are several ways we can use it to construct a Cayley graph. Five such ways are described here.
The type I construction uses the regular map directly as the Cayley graph. Its vertices correspond to elements of the group, and its edges are coloured with one colour for each group generator (and have arrows added if the order of the generator is greater than 2).
The number of Cayley graphs that can be constructed in this way may be none, one, or more than one.
We take the cube as an example of a regular map, and find that these four type I Cayley graphs can be constructed:
They are Cayley graphs of C4×C2, D8, D8 and C2×C2×C2 respectively.
The type II construction replaces each vertex of the regular map by a ring of q vertiees, where q is number of edges meeting at each vertex of the original regular map. The vertices in this ring are connected by directed edges, all of the same colour, and all directed the same way. The edges of the regular map are all retained, in another colour.
Exactly one Cayley graph can be constructed in this way.
It is the Cayley graph of the rotational symmetry group of the regular map.
Again we take the cube as an example of a regular map. Here is the type II Cayley graph:
It is a Cayley graph of S4.
A type IIa Cayley graph can only be constructed if the underlying graph of the regular map is bipartite.
It is constructed in the same way as a type II Cayley graph, except that the loops around what were adjacent vertices of the regular map are directed in alternate directions (hence the need for the graph to be bipartite).
At most one Cayley graph can be constructed in this way. Sometimes the construction may produce a graph which is not a Cayley graph.
Again we take the cube as an example of a regular map. Here is the type II Cayley graph:
It is a Cayley graph of A4×C2.
The type II construction is similar to the type II, but more elaborate. It replaces each vertex of the regular map by a ring of 2 vertiees, where q is number as above. The vertices in this ring are connected by edges in two alternating colours. The edges of the regular map are each replaced by a pair of parallel edges in a third colour. The edges around the former vertices are coloured in such a way that at each end of these parallel pairs, the edge is the same colour.
Exactly one Cayley graph can be constructed in this way.
It is a double cover of the Cayley graph of the rotational symmetry group of the regular map.
Again we take the cube as an example of a regular map. Here is the type III Cayley graph:
It is a Cayley graph of S4×C2.
A type IIIa Cayley graph can only be constructed if the underlying graph of the regular map is bipartite.
It is constructed in the same way as a type III Cayley graph, except that the loops around what were adjacent vertices of the regular map are coloured in such a way that at each end of the parallel pairs of edges (that replace the edges of the original regular map), the edge is a different colour.
At most one Cayley graph can be constructed in this way. Sometimes the construction may produce a graph which is not a Cayley graph.
Again we take the cube as an example of a regular map. Here is the type IIIa "Cayley graph":
It is not a valid Cayley graph. From some starting points, rbrg has order 1, from others it has order 2.