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 Cubic Hamiltonian Integral Cayley graph Bipartite

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.

It has chromatic number 2, chromatic index 3, diameter 4, radius 4 and girth 6. 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.

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

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.