TOPICS
Search

Ellingham-Horton Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
EllinghamHortonGraphs

A number of graphs are 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 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 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 rectilinear crossing embedding, while the 78-Ellingham-Horton graph has graph crossing number and rectilinear crossing number 25 (E. Weisstein, Oct. 20, 2025).

See also

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

Explore with Wolfram|Alpha

References

Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs." Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.Ellingham, M. N. Cycles in 3-Connected Cubics Graphs. M.Sc. 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: 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