| Horton graph | |
| Namesake: | Joseph Horton |
| Vertices: | 96 |
| Edges: | 144 |
| Automorphisms: | 96 (Z/2Z×Z/2Z×S4) |
| Girth: | 6 |
| Diameter: | 10 |
| Radius: | 10 |
| Chromatic Number: | 2 |
| Chromatic Index: | 3 |
| Properties: | Cubic Bipartite |
| Book Thickness: | 3 |
| Queue Number: | 2 |
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. It is also a 3-edge-connected graph.
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 :
(x-3)(x-1)14x4(x+1)14(x+3)(x2-5)3(x2-3)11(x2-x-3)(x2+x-3)
(x10-23x8+188x6-644x4+803x2-101)2
(x10-20x8+143x6-437x4+500x2-59)