Misplaced Pages

Harries graph

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Regular graph with 70 nodes and 105 edges
Harries graph
The Harries graph
Named afterW. Harries
Vertices70
Edges105
Radius6
Diameter6
Girth10
Automorphisms120 (S5)
Chromatic number2
Chromatic index3
Genus9
Book thickness3
Queue number2
PropertiesCubic
Cage
Triangle-free
Hamiltonian
Table of graphs and parameters

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

( x − 3 ) ( x − 1 ) 4 ( x + 1 ) 4 ( x + 3 ) ( x 2 − 6 ) ( x 2 − 2 ) ( x 4 − 6 x 2 + 2 ) 5 ( x 4 − 6 x 2 + 3 ) 4 ( x 4 − 6 x 2 + 6 ) 5 . {\displaystyle (x-3)(x-1)^{4}(x+1)^{4}(x+3)(x^{2}-6)(x^{2}-2)(x^{4}-6x^{2}+2)^{5}(x^{4}-6x^{2}+3)^{4}(x^{4}-6x^{2}+6)^{5}.\,}

History

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.

Gallery

  • The chromatic number of the Harries graph is 2. The chromatic number of the Harries graph is 2.
  • The chromatic index of the Harries graph is 3. The chromatic index of the Harries graph is 3.
  • Alternative drawing of the Harries graph. Alternative drawing of the Harries graph.
  • Alternative drawing emphasizing the graph's 4 orbits. Alternative drawing emphasizing the graph's 4 orbits.

References

  1. Weisstein, Eric W. "Harries Graph". MathWorld.
  2. Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  3. A. T. Balaban, A trivalent graph of girth ten, J. Combin. Theory Ser. B 12, 1-5. 1972.
  4. Pisanski, T.; Boben, M.; Marušič, D.; and Orbanić, A. "The Generalized Balaban Configurations." Preprint. 2001. .
  5. M. O'Keefe and P.K. Wong, A smallest graph of girth 10 and valency 3, J. Combin. Theory Ser. B 29 (1980) 91-105.
  6. Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.
Categories: