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.[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]4.[1]

The Nauru graph can also be constructed as the generalized Petersen graph G(12, 5) which is formed by the vertices of an 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 S4 and S3 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 k2 ≡ ±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 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 S4, 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 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 generalized regular polyhedra: topological surfaces 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 Dih6 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 the cubic symmetric graph is now named after him as the Foster Census and inside this list the Nauru graph is numbered as 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

  1. 1 2 3 Eppstein, D., The many faces of the Nauru graph on LiveJournal, 2007.
  2. 1 2 Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
  3. ↑ "Sloane's A110507 ", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation..
  4. ↑ Pegg, E. T.; Exoo, G. (2009), "Crossing number graphs", Mathematica Journal 11.
  5. ↑ Royle, G. F024A data
  6. ↑ Frucht, R.; Graver, J. E.; Watkins, M. E. (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society 70: 211–218, doi:10.1017/S0305004100049811.
  7. ↑ McMullen, Peter (1992), "The regular polyhedra of type {p, 3} with 2p vertices", Geometriae Dedicata 43 (3): 285–289, doi:10.1007/BF00151518.
  8. ↑ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs (PDF), IMFM preprints 1109.
  9. ↑ Foster, R. M. (1932), "Geometrical circuits of electrical networks", Transactions of the American Institute of Electrical Engineers 51: 309–317, doi:10.1109/T-AIEE.1932.5056068.
  10. ↑ Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; Star, Z (1988), The Foster Census, Charles Babbage Research Centre.
  11. ↑ Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society 56: 413–455, doi:10.1090/S0002-9904-1950-09407-5.
  12. ↑ Zacharias, M. (1941), "Untersuchungen über ebene Konfigurationen (124, 163)", Deutsche Mathematik 6: 147–170.
  13. ↑ Pegg, Ed (2003), Cubic Symmetric Graphs, Mathematical Association of America.
This article is issued from Wikipedia - version of the Monday, April 11, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.