Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Nauru graph
Summary
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.
It has chromatic number 2, chromatic index 3, diameter 4, radius 4 and girth 6. It is also a 3-vertex-connected and 3-edge-connected graph. It has book thickness 3 and queue number 2.
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.
The Nauru graph is Hamiltonian and can be described by the LCF notation : [5, −9, 7, −7, 9, −5]4.
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.
The automorphism group of the Nauru graph is a group of order 144. 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.