The many faces of the Nauru graph

The Foster census lists cubic symmetric graphs; that is, graphs in which the vertices all have three edges, and some symmetry takes any directed edge to any other directed edge.

Among these graphs, the one with 24 vertices clearly deserves a name, as Ed Pegg wrote in his online MAA column in 2003. Naming it after a person is no good: the first person to write about it was Foster [Foster, R. M. (1932), "Geometrical circuits of electrical networks", Transactions of the American Institute of Electrical Engineers 51: 309–317], who gives his name to the whole list of cubic symmetric graphs, and apparently the second was Coxeter [Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society 56: 413–455] for whom plenty of graphs are already named. For lack of a better name, I'm going to call it the Nauru graph, because the flag of Nauru has a 12-point star greatly resembling the one in one of the standard drawings of this graph.

The Nauru Drawing and Generalized Petersen Graphs

This type of drawing, with an outer polygon connected to a central star with the same number of points, forms a graph called a generalized Petersen graph; these graphs were introduced in the same Coxeter paper, and later studied by Watkins [Watkins, Mark E. (1969), "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs", Journal of Combinatorial Theory 6: 152–164]. The Nauru graph is \(GP(12,5)\): 12 for the number of points, 5 for the number of steps between each connected pair of vertices in the inner star.

A generalized Petersen graph \(GP(n,k)\) can be planar only if \(k=1\), or if \(k=2\) and \(n\) is even; neither are true in this case, so the Nauru graph has no planar embedding. From this drawing, it is also clear that the graph is very symmetric: one can form 24 different symmetries by combinations of rotations and mirror reversals of the drawings. But that turns out to be only a small fraction of the total number of its symmetries...

Tutte's Drawing and Hamiltonicity

Another slightly less symmetric drawing, which Coxeter attributes to Tutte, makes visually apparent the fact that this is a Hamiltonian graph:

This drawing allows one to express the Nauru graph in LCF notation: [5,-9,7,-7,9,-5]⁴.

Cayley Graph and xyz Drawing

Like the permutohedron and the truncated cube, the Nauru graph is a Cayley graph of the symmetric group of permutations on four elements. Its generators as a Cayley graph are the three different ways of swapping the first element with one of the three others. That is, one can form this graph by making one vertex per permutation, and connecting each vertex to the three permutations formed from it by transpositions of this type. More generally the Cayley graphs formed by transpositions of the first element, for symmetric groups of different orders, form a family studied in electrical engineering as a possible interconnection network for parallel computers, and called the star graphs [Akers, Sheldon B. & Krishnamurthy, Balakrishnan (1989), "A group-theoretic model for symmetric interconnection networks", IEEE Transactions on Computers 38 (4): 555–566] (another bad name, because a star can also refer to the complete bipartite graph \(K_{1,n}\)). Pegg suggests a nearly-equivalent way of looking at the Nauru graph: form vertices labeled by ordered triples of distinct elements from \(\{1,2,3,4\}\), and connect two such triples by an edge whenever they differ in only one position. If we use these triples as Cartesian coordinates, we get an xyz graph (seen here from a point of view near the main diagonal \(x=y=z\)):

One way of obtaining a set of points in these positions is to orthogonally project the permutohedron, in its natural 4-dimensional embedding, onto one of the three coordinate hyperplanes. However the connections between the points are quite different from the edges of the permutohedron. Coxeter notes that the Nauru graph has 144 automorphisms; its symmetry group can be factored into the direct product of the symmetric group on three elements (permutations of the three coordinates of the xyz graph representation) with the symmetric group on four elements (permutations of the four coordinate values of the representation).

Torus Drawing

The xyz graph drawing above looks sort of like a twisted torus, and in terms of the correspondence between xyz graphs and topological surface embeddings described in my paper it really is a torus, with a highly symmetric map drawn on it in which six hexagons meet three per vertex. If each vertex is labeled by a triple as above, then each hexagon is formed by choosing a fixed value for one of the positions in the triple. The 144 symmetries of the Nauru graph take any flag (incident triple of vertex, edge, and hexagonal face) to any other flag; as there are 144 flags, a symmetry can be determined by its action on the flags.

Embedding the torus in three-dimensional space causes it to lose much of its symmetry, although it doesn't have to be quite as asymmetrical as I've drawn it below; the layout shown here was chosen less to display any symmetries and more to show how the hexagonal layout above translates to an embedded torus.

A more symmetrical 3d view of the torus embedding (topologically the same, although embedded differently into 3d) may be obtained from the Nauru layout: draw two dodecagons, each wrapping around the torus, one for the outer twelve points of the Nauru layout and one for the twelve inner points. These two dodecagons divide the torus into two annular strips; draw the edges connecting the two dodecagons alternatingly between these two strips. A similar double-annulus torus embedding can be constructed for any generalized Petersen graph \(GP(4k,2k-1)\) including the Möbius–Kantor graph \(GP(8,3)\).

Genus Four Drawing and Hyperbolic Tiling

The Nauru graph also has another symmetric embedding on a more complicated surface, in which each face is a dodecagon rather than a hexagon. There are two very obvious dodecagons in the twelve-point star drawing of the graph, formed by the inner and outer twelve points; the other four dodecagons look like this:

Alternatively, these dodecagons may be seen as Petrie polygons (zigzag paths) in the hexagonal tiling of the torus. Any edge of the Nauru graph belongs to exactly two of the dodecagons, so they can be joined up to form a surface with six dodecagonal faces. As in the hexagonal tiling of the torus, the 144 symmetries of the graph take any flag of this dodecagonal tiling to any other flag. The surface formed by these six dodecagons has, by Euler's formula, genus four: that is, it is like a torus, but with four holes instead of just one.

The nicest three-dimensional embedding of this surface that I've found so far is formed as follows: start with a cube, and color opposite pairs of faces red, blue, and green. Extend a tube from each corner of the cube, connecting to the opposite corner; the three colors from one corner should continue along this tube until they meet the three colors from the opposite corner in the middle of the tube, so that each color from one corner meets the two different colors from the other corner. Then the surface of this cube with tubes has genus four, and the partition of its surface into colors partitions it into six twelve-sided faces. The points where three colors meet form the vertices of the Nauru graph, and the curves where two colors meet form its edges. But it's hard to embed this symmetrically in space, and I don't have a nice illustration of it yet.

One can unroll the hexagonal torus tiling of the Nauru graph into an infinite hexagonal tiling of the plane (in which the Nauru graph vertices repeat in a periodic pattern); the same unrolling also applies to the dodecagonal tiling, but the unrolled surface ends up being the hyperbolic plane, periodically tiled by dodecagons. If one labels the faces \(\pm 1\), \(\pm 2\), \(\pm 3\), where faces \(+i\) and \(-i\) do not touch, then the rule for labeling the corresponding faces in the infinite tiling of the hyperbolic plane is simple: for any edge of the tiling, the two non-touching faces at the endpoints of the edge have labels \(+i\) and \(-i\) for some \(i\).

Cube triple cover

Returning to Pegg's suggestion of labeling the vertices of the Nauru graph by ordered triples of distinct elements from the set \(\{1,2,3,4\}\), form groups of three triples, where the triples within each group are the cyclic rotations of each other. Then the pattern of groups, and edges connecting groups, is just the familiar cube, and this grouping forms a mapping (technically a graph homomorphism) from the Nauru graph to the cube. This map from one graph to another extends to a map from one surface to another: each of the six dodecagonal faces of the genus-four surface for the Nauru graph wraps three times around one of the faces of the cube, so this is a branched covering from one surface to another, with an order-three branch point in the middle of each cube face. This covering map stands in contrast to a result of Shen and Hu that it is impossible to embed the Nauru graph (or any of the larger star graphs that contain it) as a subgraph of a hypercube [Shen, X., and Hu, Q. (1993), "The 4-star graph is not a subgraph of any hypercube", Information Processing Letters 45(4): 199–203.].

Projective Configuration

Finally, Coxeter describes an interesting geometric representation of this graph as the Levi graph of a projective configuration, which he attributes to Zacharias [Zacharias, M. (1941), "Untersuchungen über ebene Konfigurationen (12₄, 16₃)", Deutsche Mathematik 6: 147–170]. Start with any asymmetric triangle, such as the green 30-60-90 triangle shown below. Trisect its angles; the points where the trisectors first meet (red) form an equilateral triangle, by Morley's theorem. Form a third triangle (blue), where the trisectors meet a second time. Then these three triangles are pairwise perspective, and their centers of perspective (gray) are collinear. One of these gray points is the second Morley center rediscovered in 1967 by Peter Yff. We thus have a system of twelve points (the triangle vertices and the perspective centers) and twelve lines (the nine lines connecting pairs of triangle vertices with the perspective centers, and three of the six trisectors) meeting three points per line and three lines per point. (One may obtain a larger configuration, with three points per line and four lines per point, by including also the other three trisectors and the line through the perspective centers.) The Nauru graph can be represented by these twelve points, twelve lines, and the incidences among them.

---

Comments: