From Surf Wiki (app.surf) — the open knowledge base
Ellingham–Horton graph
| Field | Value | |
|---|---|---|
| name | Ellingham–Horton graphs | |
| image | [[File:Ellingham-Horton 54-graph.svg | 220px]] |
| image_caption | The Ellingham–Horton 54-graph. | |
| namesake | Joseph Horton and Mark Ellingham | |
| vertices | 54 (54-graph) | |
| 78 (78-graph) | ||
| edges | 81 (54-graph) | |
| 117 (78-graph) | ||
| automorphisms | 32 (54-graph) | |
| 16 (78-graph) | ||
| girth | 6 (both) | |
| diameter | 10 (54-graph) | |
| 13 (78-graph) | ||
| radius | 9 (54-graph) | |
| 7 (78-graph) | ||
| chromatic_number | 2 (both) | |
| chromatic_index | 3 (both) | |
| book thickness | 3 (both) | |
| queue number | 2 (both) | |
| properties | Cubic (both) | |
| Bipartite (both) | ||
| Regular (both) |
78 (78-graph) 117 (78-graph) 16 (78-graph) 13 (78-graph) 7 (78-graph) Bipartite (both) Regular (both)
In the mathematical field of graph theory, the Ellingham–Horton graphs are two 3-regular graphs on 54 and 78 vertices: the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named after Joseph D. Horton and Mark N. Ellingham, their discoverers. These two graphs provide counterexamples to the conjecture of W. T. Tutte that every cubic 3-connected bipartite graph is Hamiltonian. The book thickness of the Ellingham-Horton 54-graph and the Ellingham-Horton 78-graph is 3 and the queue numbers 2.
The first counterexample to the Tutte conjecture was the Horton graph, published by . After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92-vertex graph by , a 78-vertex graph by , and the two Ellingham–Horton graphs.
The first Ellingham–Horton graph was published by and is of order 78. At that time it was the smallest known counterexample to the Tutte conjecture. The second Ellingham–Horton graph was published by and is of order 54. In 1989, Georges' graph, the smallest currently-known Non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.
Gallery
File:Ellingham-Horton 54-graph 2COL.svg|The chromatic number of the Ellingham–Horton 54-graph is 2. File:Ellingham-Horton 54-graph 3color edge.svg|The chromatic index of the Ellingham–Horton 54-graph is 3. File:Ellingham-Horton 78-graph 2COL.svg|The chromatic number of the Ellingham–Horton 78-graph is 2. File:Ellingham-Horton 78-graph 3color edge.svg|The chromatic index of the Ellingham–Horton 78-graph is 3.
References
References
- "Tutte Conjecture".
- Tutte, W. T.. (1971). "On the 2-factors of bicubic graphs". Discrete Mathematics.
- Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, Universität Tübingen, 2018
- Horton, J. D.. (1982). "On two-factors of bipartite regular graphs". Discrete Mathematics.
- Owens, P. J.. (1983). "Bipartite cubic graphs and a shortness exponent". Discrete Mathematics.
- Ellingham, M. N.. (1981). "Non-Hamiltonian 3-connected cubic partite graphs". Dept. of Math., Univ. Melbourne.
- (1983). "Non-Hamiltonian 3-connected cubic bipartite graphs". Journal of Combinatorial Theory, Series B.
- Georges, J. P.. (1989). "Non-hamiltonian bicubic graphs". Journal of Combinatorial Theory, Series B.
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 Ellingham–Horton 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