Nauru graph

Nauru graph

The Nauru graph is Hamiltonian.
Vertices 24
Edges 36
Radius 4
Diameter 4
Girth 6
Automorphisms 144 (S4×S3)
Chromatic number 2
Chromatic index 3
Properties Symmetric
Cayley 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 Nauru graph requires at least eight crossings in any drawing of it in the plane. It is one of five non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these five graphs is the McGee graph also known as the (3-7)-cage.[3][4]


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 a 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.

There is also a combinatorial construction of the Nauru graph. Take three distinguishable objects and place them in four distinguishable boxes, no more than one object per box. There are 24 ways to so distribute the objects, corresponding to the 24 vertices of the graph. If it is possible to go from one state to another state by moving exactly one object from its present location to an empty box, then the vertices corresponding to the two states are joined by an edge. The resulting state-transition graph is the Nauru graph.

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 , the Petersen graph , the Möbius–Kantor graph , the dodecahedral graph and the Desargues graph .

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

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 is 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.
1-planar drawing with 8 crossings.

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 a generalized regular polyhedron: a topological surface 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.


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 cubic symmetric graphs is now named after him the Foster Census and inside this list the Nauru graph is numbered 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]


  1. 1 2 3 Eppstein, D., The many faces of the Nauru graph on LiveJournal, 2007.
  2. 1 2 Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
  3. "Sloane's A110507". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation..
  4. Pegg, E. T.; Exoo, G. (2009), "Crossing number graphs", Mathematica Journal, 11.
  5. Royle, G. F024A data
  6. 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.
  7. McMullen, Peter (1992), "The regular polyhedra of type {p, 3} with 2p vertices", Geometriae Dedicata, 43 (3): 285–289, doi:10.1007/BF00151518.
  8. Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs (PDF), IMFM preprints, 1109.
  9. 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.
  10. Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; Star, Z (1988), The Foster Census, Charles Babbage Research Centre.
  11. 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.
  12. Zacharias, M. (1941), "Untersuchungen über ebene Konfigurationen (124, 163)", Deutsche Mathematik, 6: 147–170.
  13. Pegg, Ed (2003), Cubic Symmetric Graphs, Mathematical Association of America.
This article is issued from Wikipedia - version of the 6/26/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.