| 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 |
| Book thickness | 3 |
| Queue number | 2 |
| Properties | Symmetric Cubic Hamiltonian Integral Cayley graph Bipartite |
| Table of graphs and parameters | |
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. It has book thickness 3 and queue number 2.[3]
The Nauru graph requires at least eight crossings in any drawing of it in the plane. It is one of three non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these three graphs is the McGee graph, also known as the (3-7)-cage.[4][5]
- ^ Cite error: The named reference
DE1was invoked but never defined (see the help page). - ^ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
- ^ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
- ^ Sloane, N. J. A. (ed.). "Sequence A110507 (Number of nodes in the smallest cubic graph with crossing number n)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation..
- ^ Pegg, E. T.; Exoo, G. (2009), "Crossing number graphs", Mathematica Journal, 11 (2), doi:10.3888/tmj.11.2-2, archived from the original on 2019-03-06, retrieved 2010-01-02.