Nauru graph

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
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]

Construction

The Nauru graph is Hamiltonian and can be described by the LCF notation : [5, −9, 7, −7, 9, −5]⁴.^[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.^[6] It is isomorphic to the direct product of the symmetric groups S₄ and S₃ 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 k² ≡ ±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).^[7] 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 S₄, 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 embedding on a torus formed by gluing opposite edges of a regular hexagon
Generalized Petersen graph, colored and labeled as a Cayley graph of S₄
Adjacency matrix. Each edge is represented by two symmetrically-placed entries in the same color
1-planar drawing with 8 crossings
24 orientations of a rolling octahedron on a triangular grid, drawn on a hexagonal torus
24 configurations of a 2×2×2 Rubik's cube reachable via 180° half-turns

Topological properties

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.^[8]

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

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.^[9] 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 Dih₆ 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.^[10] 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.^[11] 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.^[12]^[13]

In 2003, Ed Pegg wrote in his online MAA column that F24A deserves a name but did not propose one.^[14] 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, 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.
^ 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.
^ Royle, G. F024A data Archived 2011-03-06 at the Wayback Machine
^ Frucht, R.; Graver, J. E.; Watkins, M. E. (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society, 70 (2): 211–218, Bibcode:1971PCPS...70..211F, doi:10.1017/S0305004100049811, S2CID 122686848.
^ McMullen, Peter (1992), "The regular polyhedra of type {p, 3} with 2p vertices", Geometriae Dedicata, 43 (3): 285–289, doi:10.1007/BF00151518, S2CID 119591683.
^ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs (PDF), IMFM preprints, vol. 1109.
^ Foster, R. M. (1932), "Geometrical circuits of electrical networks", Transactions of the American Institute of Electrical Engineers, 51 (2): 309–317, doi:10.1109/T-AIEE.1932.5056068, S2CID 51638449.
^ 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 (5): 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.