I've now run my xyz-graph testing code on the graphs of up to 56 vertices in the Foster Census of cubic symmetric graphs. That's about the limit of how large a graph it can handle before I run out of patience.

My program found that graphs \( F_8 \) (the cube), \( F_{18} \) (the Pappus graph), \( F_{24} \) (the Generalized Petersen graph \( G(12,5) \)), \( F_{32} \) (the Dyck graph), \( F_{40} \) (the double cover of the dodecahedron), \( F_{42} \), \( F_{50} \), and \( F_{54} \) can be represented as xyz graphs. (Here, by convention, \( F_{k} \) denotes the cubic symmetric graph with \( k \) vertices; for each of the graphs listed, there is no other cubic symmetric graph with the same size.)

Of these graphs, \( F_{8} \), \( F_{18} \), \( F_{32} \), and \( F_{50} \) can be explained as the xyz graphs formed by the point set \[ \{ (x,y,z)\mid 0\le x,y,z\lt n \mbox{ and } x+y+z=0\mbox{ or } 1 \bmod n \} \] described in my previous post. The result is not just a symmetric graph, but a regular map: there are symmetries taking any vertex to any other vertex, any edge to any other edge, any face (set of points in an axis-aligned plane) to any other face, and any flag (incident triple of vertex, edge, and face) to any other flag.

\( F_{18} \), \( F_{24} \), \( F_{42} \), and \( F_{54} \) can be explained as instances of the following construction: 3-color the hexagonal tiling of the plane, draw a 60-120 degree rhombus having its vertices at the centers of four tiles of the same color, and glue opposite pairs of rhombus edges to form a torus. The resulting torus map is transitive on vertices, edges, faces, and on incident pairs of two of these three types of objects, but it is not necessarily transitive on flags — e.g., \( F_{42} \) is not regular. The same construction can be performed without the color restriction on the corners of the rhombus, and leads to symmetric maps that do not correspond to xyz graph representations; for instance, \( F_{32} \) can be drawn as a regular but not 3-face-colorable torus map in this way.

Rhombi in a hexagonal tiling of the plane

That leaves \( F_{40} \), which can't be explained as an instance of either construction. It's unusual in another respect, too: while the other graphs all have only one way of being represented as an xyz graph (up to permutation of coordinates and of values within each coordinate) \( F_{40} \) has twelve. The reason is that, while it's a symmetric graph and an xyz graph, its xyz graph representation doesn't form a regular map, so symmetries of the graph will take one xyz-graph representation to a representation that looks the same visually but has the vertices differently arranged. For instance, each representation as an xyz graph has four decagons and ten octagons; the four decagons form a partition of the vertices into four sets of ten vertices, but different representations differ in which partition of this type they use. Here's a drawing:

Representation of F40 as an xyz graph

It's also possible to describe the corresponding map geometrically in terms of the dodecahedron that \( F_{40} \) double covers. The four decagons correspond to two opposite pentagonal faces (double covered to make decagons) and the equator between them (two separate cycles in the double cover). Each octagonal face corresponds to the boundary of an adjacent pair of pentagons, one on each side of the equator; there are ten such pairs, which partition the faces adjacent to the equator into five pairs in two different ways. In the double cover, these rings of five face-pairs turn into rings of ten octagons; choose five alternating octagons from each ring. The decagons get a single color, and the five chosen octagons from the same ring get a single color. There are six ways to pick two opposite faces of the dodecahedron to form this construction, two ways of picking alternating octagons from one ring, and once you've made that choice there's only one matching way of picking alternating octagons from the other ring, for a total of twelve xyz graph representations as already calculated.