TOPICS
Search

Nauru Graph


NauruGraphEmbeddings

The Nauru graph is the name given by Eppstein (2007) to the generalized Petersen graph GP(12,5) on 24 nodes and 36 edges which is also cubic symmetric graph F_(024)A, the permutation star graph of order 4, the honeycomb toroidal graph HTG(2,12,6), the Levi graph of the Coxeter configuration 12_3 (perhaps better termed the "Nauru configuration"), and the rolling polyhedron graph for the regular octahedron.

NauruFlag

The name of the graph derives from the resemblance of the central star polygon in the generalized Petersen embedding to the 12-point star on the flag of the Pacific island nation of Nauru.

NauruGraphMinimalCrossing

The Nauru graph is one of three cubic graphs on 24 nodes with smallest possible graph crossing number of 8 (another being the McGee graph), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019). It also has rectilinear crossing number 8. A number of minimal crossing embeddings are show above.

The configurations of a 2×2×2 Rubik's cube reachable using only half twists form a Nauru graph.

NauruGraphUnitDistance

It is also a unit-distance graph, as illustrated above in a number of unit-distance embeddings. The first was given by Žitnik et al. (2010) and the second is due to Gerbracht (pers. comm., Jan. 4, 2010).

The Nauru graph is implemented in the Wolfram Language as GraphData["NauruGraph"].


See also

Coxeter Configuration, Cubic Symmetric Graph, Generalized Petersen Graph, Honeycomb Toroidal Graph, Permutation Star Graph, Smallest Cubic Crossing Number Graph

Explore with Wolfram|Alpha

References

Clancy, K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.Eppstein, D. "The Many Faces of the Nauru Graph." Dec. 12, 2007. http://11011110.livejournal.com/124705.html.Foster, R. M. "Geometrical Circuits of Electrical Networks." Trans. Amer. Inst. Elec. Engin. 51, 309-317, 1932.Pegg, E. Jr. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.

Cite this as:

Weisstein, Eric W. "Nauru Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NauruGraph.html

Subject classifications