Horton graph
| Horton graph | |
|---|---|
 The Horton graph | |
| Named after | Joseph Horton |
| Vertices | 96 |
| Edges | 144 |
| Radius | 10 |
| Diameter | 10 |
| Girth | 6 |
| Automorphisms | 96 (Z/2Z×Z/2Z×S4) |
| Chromatic number | 2 |
| Chromatic index | 3 |
| Book thickness | 3 |
| Queue number | 2 |
| Properties | Cubic Bipartite |
| Table of graphs and parameters | |
In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton.[1] Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian.[2][3]
After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92 vertex graph by Horton published in 1982, a 78 vertex graph by Owens published in 1983, and the two Ellingham-Horton graphs (54 and 78 vertices).[4][5]
The first Ellingham-Horton graph was published by Ellingham in 1981 and was of order 78.[6] At that time, it was the smallest known counterexample to the Tutte conjecture. The second one was published by Ellingham and Horton in 1983 and was of order 54.[7] In 1989, Georges' graph, the smallest currently-known non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.[8]
As a non-Hamiltonian cubic graph with many long cycles, the Horton graph provides good benchmark for programs that search for Hamiltonian cycles.[9]
The Horton graph has chromatic number 2, chromatic index 3, radius 10, diameter 10, girth 6, book thickness 3[10] and queue number 2.[10] It is also a 3-edge-connected graph.
Algebraic properties
The automorphism group of the Horton graph is of order 96 and is isomorphic to Z/2Z×Z/2Z×S4, the direct product of the Klein four-group and the symmetric group S4.
The characteristic polynomial of the Horton graph is : [math]\displaystyle{ (x-3) (x-1)^{14} x^4 (x+1)^{14} (x+3) (x^2-5)^3 (x^2-3)^{11}(x^2-x-3) (x^2+x-3) }[/math] [math]\displaystyle{ (x^{10}-23 x^8+188 x^6-644 x^4+803 x^2-101)^2 }[/math] [math]\displaystyle{ (x^{10}-20 x^8+143 x^6-437 x^4+500 x^2-59) }[/math].
Gallery
The chromatic number of the Horton graph is 2.
The chromatic index of the Horton graph is 3.
The Ellingham-Horton 54-graph, a smaller counterexample to the Tutte conjecture.
References
- ↑ "Horton Graph". https://mathworld.wolfram.com/HortonGraph.html.
- ↑ Tutte, W. T. "On the 2-Factors of Bicubic Graphs." Discrete Math. 1, 203-208, 1971/72.
- ↑ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
- ↑ Horton, J. D. "On Two-Factors of Bipartite Regular Graphs." Discrete Math. 41, 35-41, 1982.
- ↑ Owens, P. J. "Bipartite Cubic Graphs and a Shortness Exponent." Discrete Math. 44, 327-330, 1983.
- ↑ Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
- ↑ Ellingham, M. N. and Horton, J. D. "Non-Hamiltonian 3-Connected Cubic Bipartite Graphs." J. Combin. Th. Ser. B 34, 350-353, 1983.
- ↑ Georges, J. P. (1989), "Non-hamiltonian bicubic graphs", Journal of Combinatorial Theory, Series B 46 (1): 121–124, doi:10.1016/0095-8956(89)90012-9.
- ↑ V. Ejov, N. Pugacheva, S. Rossomakhine, P. Zograf "An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs" arXiv:math/0610779v1.
- ↑ 10.0 10.1 Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
 |  |
