TOPICS
Search

Horton Graphs


HortonGraphs

There are (at least) two graphs associated with Horton, illustrated above. The first is a graph on 96 nodes providing a counterexample to the Tutte conjecture that every 3-regular 3-connected bipartite graph is Hamiltonian (left figure above). The second is a smaller counterexample on 92 nodes (right figure above). (A number of even smaller counterexamples have subsequently been found.)

These graphs are implemented in the Wolfram Language as GraphData["HortonGraph96"] and GraphData["HortonGraph92"], respectively.


See also

Bicubic Graph, Ellingham-Horton Graphs, Nonhamiltonian Graph, Tutte Conjecture

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 242, 1976.Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs." Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.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, 1982.Ellingham, M. N. and Horton, J. D. "Non-Hamiltonian 3-Connected Cubic Bipartite Graphs." J. Combin. Th. Ser. B 34, 350-353, 1983.Horton, J. D. "On Two-Factors of Bipartite Regular Graphs." Disc. Math. 41, 35-41, 1982.Owens, P. J. "Bipartite Cubic Graphs and a Shortness Exponent." Disc. Math. 44, 327-330, 1983.

Cite this as:

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

Subject classifications