TOPICS
Search

Ellingham-Horton Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
EllinghamHortonGraphs

The term "Ellingham-Horton graphs" is used in this work for three graphs associated with Ellingham and Horton. The smallest has 18 vertices, while two larger graphs on 54 and 78 nodes are examples of 3-connected bicubic nonhamiltonian graphs, and therefore provide counterexamples to the Tutte bicubic graph conjecture.

EllinghamHortonGraphB

Ellingham and Horton (1983) constructed the 54-Ellingham-Horton graph using two copies of the 18-node bicubic graph B illustrated above, deleting the two dashed edges from each and rejoining the resulting vertices of degree 2 to the other components. No Hamiltonian cycle in B contains both specified edges. Georges (1989) used B as the basis of his construction of the Georges-Kelmans graph. Each specified edge is subdivided twice in the construction, and two copies of the resulting graph are combined (Grünbaum 2009, pp. 310-311). However, Georges's published drawing of graph B omits one of the two specified edges (Grünbaum 2009, p. 317).

EllinghamHortonGraphMinimalCrossing

The 54-Ellingham-Horton graph has graph crossing number and rectilinear crossing number 14, illustrated above in a bilaterally symmetric minimal straight line drawing (E. Weisstein, Oct. 20, 2025). The 78-Ellingham-Horton graph has graph crossing number 18 (E. Weisstein, Oct. 1, 2026). Its rectilinear crossing number is at most 25 (E. Weisstein, Oct. 20, 2025).

See also

Bicubic Nonhamiltonian Graph, Georges-Kelmans Graph, Horton Graphs, Tutte Bicubic Graph Conjecture

Explore with Wolfram|Alpha

References

Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs." Dept. of Math. Research Report No. 28. Melbourne, Australia: University of Melbourne, 1981.Ellingham, M. N. "Cycles in 3-Connected Cubics Graphs." Master's thesis. Melbourne, Australia: University of Melbourne, June 1982a.Ellingham, M. N. "Constructing Certain Cubic Graphs." In Combinatorial Mathematics, IX: Proceedings of the Ninth Australian Conference held at the University of Queensland, Brisbane, August 24-28, 1981 (Ed. E. J. Billington, S. Oates-Williams, and A. P. Street). Berlin, Germany: Springer-Verlag, pp. 252-274, 1982b.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. "Non-Hamiltonian Bicubic Graphs." J. Combin. Th. B 46, 121-124, 1989.Grünbaum, B. Configurations of Points and Lines. Providence, RI: Amer. Math. Soc., pp. 310-311 and 317, 2009.House of Graphs. Ellingham-Horton Graphs. B Subgraph of 54 Vertex Non-Hamiltonian 3 Connected Cubic Bipartite Graphs, Ellingham Horton Graph 54, and Ellingham Horton Graph 78.

Referenced on Wolfram|Alpha

Ellingham-Horton Graphs

Cite this as:

Weisstein, Eric W. "Ellingham-Horton Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Ellingham-HortonGraphs.html

Subject classifications