TOPICS
Search

Ellingham-Horton Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
EllinghamHortonGraphs

There are (at least) two graphs associated with Ellingham and Horton. These graphs on 54 and 78 nodes respectively, illustrated above, are examples of 3-connected bicubic nonhamiltonian graphs, and therefore provide counterexamples to the Tutte conjecture.

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, 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.

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