TOPICS
Search

Bicubic Nonhamiltonian Graph


A bicubic nonhamiltonian graph is a bicubic (i.e., bipartite cubic graph) that is nonhamiltonian (i.e., that does not possess a Hamiltonian cycle).

HortonGraph

Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian, an assertion known as the Tutte conjecture. The Horton graph on 96 nodes, illustrated above, provided the first counterexample (Bondy and Murty 1976, p. 240).

NonhamiltonianBicubicGraphs

Horton (1982) subsequently found a counterexample on 92 nodes, and two smaller (nonisomorphic) counterexamples on 78 nodes were found by Ellingham (1981, 1982b) and Owens (1983). Ellingham and Horton (1983) subsequently found a counterexample graph on 54 nodes and 81 edges. The smallest currently known counterexample is the 50-node Georges graph (Georges 1989; Grünbaum 2006, 2009).

These small known counterexamples are summarized in the following table and illustrated above.

Vnamereference
50Georges graphGeorges (1989), Grünbaum (2006, 2009)
5454-Ellingham-Horton graphEllingham and Horton (1983)
7878-Ellingham-Horton graphEllingham (1981, 1982)
7878-Owens graphOwens (1983)
9292-Horton graphHorton (1982)
9696-Horton graphBondy and Murty (1976)

See also

Bicubic Graph, Cubic Nonhamiltonian Graph, Ellingham-Horton Graphs, Georges Graph, Horton Graphs, Nonhamiltonian Graph, Owens Graphs, Tutte Conjecture

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 240, 1976.Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin: Springer-Verlag, pp. 487-488, 2008.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.Gropp, H. "Configurations and the Tutte Conjecture." Ars. Combin. A 29, 171-177, 1990.Grünbaum, B. "3-Connected Configurations (n_3) with No Hamiltonian Circuit." Bull. Inst. Combin. Appl. 46, 15-26, 2006.Grünbaum, B. Configurations of Points and Lines. Providence, RI: Amer. Math. Soc., p. 311, 2009.Horton, J. D. "On Two-Factors of Bipartite Regular Graphs." Discr. Math. 41, 35-41, 1982.Owens, P. J. "Bipartite Cubic Graphs and a Shortness Exponent." Disc. Math. 44, 327-330, 1983.Tutte, W. T. "On the 2-Factors of Bicubic Graphs." Discr. Math. 1, 203-208, 1971.

Cite this as:

Weisstein, Eric W. "Bicubic Nonhamiltonian Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BicubicNonhamiltonianGraph.html

Subject classifications