From Surf Wiki (app.surf) — the open knowledge base
Harries graph
Regular graph with 70 nodes and 105 edges
Regular graph with 70 nodes and 105 edges
| Field | Value |
|---|---|
| name | Harries graph |
| image | Harries graph.svg |
| image_caption | The Harries graph |
| namesake | W. Harries |
| vertices | 70 |
| edges | 105 |
| automorphisms | 120 (S) |
| genus | 9 |
| girth | 10 |
| diameter | 6 |
| radius | 6 |
| chromatic_number | 2 |
| chromatic_index | 3 |
| properties | Cubic |
| Cage | |
| Triangle-free | |
| Hamiltonian | |
| book thickness | 3 |
| queue number | 2 |
Cage Triangle-free Hamiltonian
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-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
File:Harries graph 2COL.svg|The chromatic number of the Harries graph is 2. File:Harries graph 3color edge.svg|The chromatic index of the Harries graph is 3. File:harries_graph_alternative_drawing.svg|Alternative drawing of the Harries graph. File:Harries graph petersen drawing.jpg|Alternative drawing emphasizing the graph's 4 orbits.
References
References
- "Harries Graph".
- Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018
- A. T. Balaban, A trivalent graph of girth ten, J. Combin. Theory Ser. B 12, 1-5. 1972.
- Pisanski, T.; Boben, M.; Marušič, D.; and Orbanić, A. "The Generalized Balaban Configurations." Preprint. 2001. [http://citeseer.ist.psu.edu/448980.html].
- 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.
- Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about Harries graph — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report