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 GraphSearch.
Concept
Harries graph
Summary
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
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.
Image:Harries graph 2COL.svg|The chromatic number of the Harries graph is 2.
Image:Harries graph 3color edge.svg|The chromatic index of the Harries graph is 3.
Image:harries_graph_alternative_drawing.svg|Alternative drawing of the Harries graph.
Image:Harries graph petersen drawing.jpg|Alternative drawing emphasizing the graph's 4 orbits.
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.