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

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

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

References