Ellingham–Horton graph

{{infobox graph

| name = Ellingham–Horton graphs

| image = 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)

}}

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.{{MathWorld|urlname=TutteConjecture|title=Tutte Conjecture}} 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.{{citation|last=Tutte|first=W. T.|title=On the 2-factors of bicubic graphs|journal=Discrete Mathematics|volume=1|issue=2|pages=203–208|year=1971|doi=10.1016/0012-365X(71)90027-6|doi-access=free}}. The book thickness of the Ellingham-Horton 54-graph and the Ellingham-Horton 78-graph is 3 and the queue numbers 2.Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, Universität Tübingen, 2018

The first counterexample to the Tutte conjecture was the Horton graph, published by {{harvtxt|Bondy|Murty|1976}}.{{citation|last1=Bondy|first1=J. A.|author1-link=John Adrian Bondy|last2=Murty|first2=U. S. R.|author2-link=U. S. R. Murty|title=Graph Theory with Applications|location=New York|publisher=North Holland|year=1976|isbn=0-444-19451-7|url=https://archive.org/details/graphtheorywitha0000bond/page/240|page=[https://archive.org/details/graphtheorywitha0000bond/page/240 240]|url-status=}}

After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92-vertex graph by {{harvtxt|Horton|1982}},{{citation|last=Horton|first=J. D.|title=On two-factors of bipartite regular graphs|journal=Discrete Mathematics|volume=41|issue=1|doi=10.1016/0012-365X(82)90079-6|pages=35–41|year=1982|doi-access=free}}. a 78-vertex graph by {{harvtxt|Owens|1983}},{{citation|last=Owens|first=P. J.|title=Bipartite cubic graphs and a shortness exponent|journal=Discrete Mathematics|volume=44|issue=3|doi=10.1016/0012-365X(83)90201-7|pages=327–330|year=1983|doi-access=}}. and the two Ellingham–Horton graphs.

The first Ellingham–Horton graph was published by {{harvtxt|Ellingham|1981}} and is of order 78.{{citation|last=Ellingham|first=M. N.|title=Non-Hamiltonian 3-connected cubic partite graphs|series=Research Report 28|publisher=Dept. of Math., Univ. Melbourne|location=Melbourne|year=1981}}. At that time it was the smallest known counterexample to the Tutte conjecture. The second Ellingham–Horton graph was published by {{harvtxt|Ellingham|Horton|1983}} and is of order 54.{{citation|last1=Ellingham|first1=M. N.|last2=Horton|first2=J. D.|title=Non-Hamiltonian 3-connected cubic bipartite graphs|journal=Journal of Combinatorial Theory, Series B|volume=34|issue=3|doi=10.1016/0095-8956(83)90046-1|pages=350–353|year=1983|doi-access=free}}. In 1989, Georges' graph, the smallest currently-known Non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.{{citation|last=Georges|first=J. P.|title=Non-hamiltonian bicubic graphs|journal=Journal of Combinatorial Theory, Series B|volume=46|issue=1|doi=10.1016/0095-8956(89)90012-9|pages=121–124|year=1989|doi-access=}}.