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.
Construction
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 connec

Official source

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.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications

No results

Related units

Related lectures

No results

No results

Related concepts

No results

Related courses

No results

Related people

No results