Ellingham–Horton graphs | |
---|---|
Named after | Joseph Horton and Mark Ellingham |
Vertices | 54 (54-graph) 78 (78-graph) |
Edges | 81 (54-graph) 117 (78-graph) |
Radius | 9 (54-graph) 7 (78-graph) |
Diameter | 10 (54-graph) 13 (78-graph) |
Girth | 6 (both) |
Automorphisms | 32 (54-graph) 16 (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) |
Table of graphs and parameters |
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. [1] 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. [2] The book thickness of the Ellingham-Horton 54-graph and the Ellingham-Horton 78-graph is 3 and the queue numbers 2. [3]
The first counterexample to the Tutte conjecture was the Horton graph, published by Bondy & Murty (1976). [4] After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92-vertex graph by Horton (1982), [5] a 78-vertex graph by Owens (1983), [6] and the two Ellingham–Horton graphs.
The first Ellingham–Horton graph was published by Ellingham (1981) and is of order 78. [7] At that time it was the smallest known counterexample to the Tutte conjecture. The second Ellingham–Horton graph was published by Ellingham & Horton (1983) and is of order 54. [8] In 1989, Georges' graph, the smallest currently-known Non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices. [9]
Ellingham–Horton graphs | |
---|---|
Named after | Joseph Horton and Mark Ellingham |
Vertices | 54 (54-graph) 78 (78-graph) |
Edges | 81 (54-graph) 117 (78-graph) |
Radius | 9 (54-graph) 7 (78-graph) |
Diameter | 10 (54-graph) 13 (78-graph) |
Girth | 6 (both) |
Automorphisms | 32 (54-graph) 16 (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) |
Table of graphs and parameters |
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. [1] 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. [2] The book thickness of the Ellingham-Horton 54-graph and the Ellingham-Horton 78-graph is 3 and the queue numbers 2. [3]
The first counterexample to the Tutte conjecture was the Horton graph, published by Bondy & Murty (1976). [4] After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92-vertex graph by Horton (1982), [5] a 78-vertex graph by Owens (1983), [6] and the two Ellingham–Horton graphs.
The first Ellingham–Horton graph was published by Ellingham (1981) and is of order 78. [7] At that time it was the smallest known counterexample to the Tutte conjecture. The second Ellingham–Horton graph was published by Ellingham & Horton (1983) and is of order 54. [8] In 1989, Georges' graph, the smallest currently-known Non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices. [9]