# Cayley Graphs derived from Regular Maps

This page describes how any regular map can be converted to a Cayley graph of its rotational symmetry group, and to a Cayley graph of its full symmetry group.

## First example: the Octahedron

The diagram to the right shows an octahedron, which is a regular map.

To convert this to a Cayley graph, we "truncate" each vertex, replacing it by a cycle of arcs, shown in black. The size of the cycle is the valency of the vertex. We also replace the edges of the original regular map by red arcs of the Cayley graph.

The result is the Cayley graph shown to the right, which is for the rotational symmetry group of the original regular map. In this case it is S4.

The nodes of this Cayley graph correspond to the darts of the regular map. The group whose Cayley graph it is, permutes these darts.

We can also convert a regular map to a larger Cayley graph. Instead of replacing each n-valent vertex to an n-gon of directed arcs, we replace it by a 2n-gon of alternate red and green arcs. We also replace each edge of the original regular map by a pair of blue arcs, ensuring that these two blue edges are connected together at each end by a red arc.

The result is the Cayley graph shown to the right, which is for the full symmetry group of the original regular map. In this case it is S4 ×C2.

The nodes of this Cayley graph correspond to the flags of the regular map. The group whose Cayley graph it is, permutes these flags.

## Second example: {4,4}(2,1)

The diagram to the right shows {4,4}(2,1), another regular map.

As above, to convert this to a Cayley graph, we "truncate" each vertex, replacing it by a cycle of arcs, shown in black. We also replace the edges of the original regular map by red arcs of the Cayley graph.

The result is the Cayley graph shown to the right, which is for the rotational symmetry group of the original regular map. In this case it is the Frobenius group of order 20.

We can also try to convert this regular map to a larger Cayley graph, as above, with a node of the graph corresponding to each flag of the original regular map.

The result is the graph shown to the right. However, we find that this is not a valid Cayley graph. If we name the generators of this supposed Cayley graph r for the red arcs, g for the green arcs, and b for the blue arcs, we find that
(gbr)10 = 1
(gbr)7 = rgr
(rgr)2 = 1
This is not consistent. This "Cayley graph" is invalid.

We have not obtained a valid Cayley graph here because the original regular map was chiral. It was dart-transitive, but not flag-transitive. When we constructed a Cayley graph for its rotational symmetry group, above, we got a valid Cayley graph for its rotational symmetry group, Frob20. But when we tried to construct one for its full symmetry group, with 40 elements including reflections, we did not get a valid Cayley graph, as the 40-element group that it would show does not exist.