Harries graph
Regular graph with 70 nodes and 105 edges
In the mathematical field of graph theory, the Harries graph or Harries (3-10)-cage is a 3-regular, undirected graph with 70 vertices and 105 edges.
The Harries graph has chromatic number 2, chromatic index 3, radius 6, diameter 6, girth 10 and is Hamiltonian. It is also a 3-vertex-connected and 3-edge-connected, non-planar, cubic graph. It has book thickness 3 and queue number 2.
The characteristic polynomial of the Harries graph is
01History
In 1972, A. T. Balaban published a (3-10)-cage graph, a cubic graph that has as few vertices as possible for girth 10. It was the first (3-10)-cage discovered but it was not unique.
The complete list of (3-10)-cage and the proof of minimality was given by O'Keefe and Wong in 1980. There exist three distinct (3-10)-cage graphs, the Balaban 10-cage, the Harries graph and the Harries-Wong graph. Moreover, the Harries-Wong graph and Harries graph are cospectral graphs.
Sources and credits
This article is adapted from the Wikipedia article “Harries graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Images, from Wikimedia Commons:
- Harries graph.svg by Koko90, CC BY-SA 3.0
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.