Nauru graph

In the mathematical field of graph theory, the Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.[1]

It has chromatic number 2, chromatic index 3, diameter 4, radius 4 and girth 6.[2] It is also a 3-vertex-connected and 3-edge-connected graph.

The smallest cubic graphs with crossing numbers 1–8 are known (sequence A110507 in OEIS). The smallest 8-crossing graph is the Nauru graph. There exists 5 non-isomorphic cubic graphs of order 24 with crossing number 8.[3] One of them is the McGee graph also known as the (3-7)-cage.[4]

Construction

The Nauru graph is Hamiltonian and can be described by the LCF notation : [5, −9, 7, −7, 9, −5]4.[1]

The Nauru graph can also be constructed as the generalized Petersen graph G(12, 5) which is formed by the vertices of an dodecagon, connected to the vertices of a twelve-point star in which each point of the star is connected to the points five steps away from it.
Algebraic properties

The automorphism group of the Nauru graph is a group of order 144.[5] It is isomorphic to the direct product of the symmetric groups S4 and S3 and acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the Nauru graph is a symmetric graph (though not distance transitive). It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the Foster census, the Nauru graph is the only cubic symmetric graph on 24 vertices.[2]

The generalized Petersen graph G(n,k) is vertex-transitive if and only if n = 10 and k =2 or if k2 ≡ ±1 (mod n) and is edge-transitive only in the following seven cases: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5).[6] So the Nauru graph is one of only seven symmetric Generalized Petersen graphs. Among these seven graphs are the cubical graph G(4,1), the Petersen graph G(5,2), the Möbius–Kantor graph G(8,3), the dodecahedral graph G(10,2) and the Desargues graph G(10,3).

The Nauru graph is a Cayley graph of S4, the symmetric group of permutations on four elements, generated by the three different ways of swapping the first element with one of the three others : (1 2), (1 3) and (1 4).

The characteristic polynomial of the Nauru graph is equal to

\( (x-3) (x-2)^6 (x-1)^3 x^4 (x+1)^3 (x+2)^6 (x+3),\ \)

making it an integral graph—a graph whose spectrum consists entirely of integers.
Symmetric torus embedding
The torus is formed, topologically, by gluing opposite edges of a regular hexagon to each other.

Generalized Petersen graph
The colors and permutations indicate, that it's a Cayley graph of S4.

Adjacency matrix
Each edge is represented by two entries in the same color, which are symmetric to the main diagonal.
Topological properties
A symmetric embedding of the Nauru graph on a genus-4 surface, with six dodecagonal faces.

The Nauru graph has two different embeddings as generalized regular polyhedra: topological surfaces partitioned into edges, vertices, and faces in such a way that there is a symmetry taking any flag (an incident triple of a vertex, edge, and face) into any other flag.[7]

One of these two embeddings forms a torus, so the Nauru graph is a toroidal graph: it consists of 12 hexagonal faces together with the 24 vertices and 36 edges of the Nauru graph. The dual graph of this embedding is a symmetric 6-regular graph with 12 vertices and 36 edges.

The other symmetric embedding of the Nauru graph has six dodecagonal faces, and forms a surface of genus 4. Its dual is not a simple graph, since each face shares three edges with four other faces, but a multigraph. This dual can be formed from the graph of a regular octahedron by replacing each edge with a bundle of three parallel edges.

The set of faces of any one of these two embeddings is the set of Petrie polygons of the other embedding.
Geometric properties
The Nauru graph as a unit distance graph, from Žitnik, Horvat & Pisanski (2010).

As with all generalized Petersen graphs, the Nauru graph can be represented by points in the plane in such a way that adjacent vertices are at unit distance apart; that is, it is a unit distance graph.[8] It and the prisms are the only generalized Petersen graphs G(n,p) that cannot be so represented in such a way that the symmetries of the drawing form a cyclic group of order n. Instead, its unit distance graph representation has the dihedral group Dih6 as its symmetry group.
History

The first person to write about the Nauru graph was R. M. Foster in an effort to collect all the cubic symmetric graphs.[9] The whole list of the cubic symmetric graph is now named after him as the Foster Census and inside this list the Nauru graph is numbered as graph F24A but has no specific name.[10] In 1950, H. S. M. Coxeter cited the graph a second time, giving the Hamiltonian representation used to illustrate this article and describing it as the Levi graph of a projective configuration discovered by Zacharias.[11][12]

In 2003, Ed Pegg wrote in his online MAA column that F24A deserves a name but did not propose one.[13] Finally, in 2007, David Eppstein used the name Nauru graph because the flag of the Republic of Nauru has a 12-point star similar to the one that appears in the construction of the graph as a generalized Petersen graph.[1]
References

^ a b c Eppstein, D., The many faces of the Nauru graph on LiveJournal, 2007.
^ a b Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
^ Pegg, E. T.; Exoo, G. (2009), "Crossing number graphs", Mathematica Journal 11.
^ Weisstein, Eric W., "Graph Crossing Number" from MathWorld.
^ Royle, G. F024A data
^ Frucht, R.; Graver, J. E.; Watkins, M. E. (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society 70: 211–218, doi:10.1017/S0305004100049811.
^ McMullen, Peter (1992), "The regular polyhedra of type {p, 3} with 2p vertices", Geometriae Dedicata 43 (3): 285–289, doi:10.1007/BF00151518.
^ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs, IMFM preprints, 1109.
^ Foster, R. M. (1932), "Geometrical circuits of electrical networks", Transactions of the American Institute of Electrical Engineers 51: 309–317, doi:10.1109/T-AIEE.1932.5056068.
^ Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; Star, Z (1988), The Foster Census, Charles Babbage Research Centre.
^ Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society 56: 413–455, doi:10.1090/S0002-9904-1950-09407-5.
^ Zacharias, M. (1941), "Untersuchungen über ebene Konfigurationen (124, 163)", Deutsche Mathematik 6: 147–170.
^ Pegg, Ed (2003), Cubic Symmetric Graphs, Mathematical Association of America.