Tutte Conjecture
المؤلف:
Bondy, J. A. and Murty, U. S. R
المصدر:
Graph Theory with Applications. New York: North Holland
الجزء والصفحة:
...
29-4-2022
3068
Tutte Conjecture
Tutte (1971/72) conjectured that there are no 3-connected nonhamiltonian bicubic graphs. However, a counterexample was found by J. D. Horton in 1976 (Gropp 1990), and several smaller counterexamples are now known.
Known small counterexamples are summarized in the following table and illustrated above.
 |
name |
reference |
| 50 |
Georges graph |
Georges (1989), Grünbaum (2006, 2009) |
| 54 |
Ellingham-Horton 54-graph |
Ellingham and Horton (1983) |
| 78 |
Ellingham-Horton 78-graph |
Ellingham (1981, 1982) |
| 78 |
Owens graph |
Owens (1983) |
| 92 |
Horton 92-graph |
Horton (1982) |
| 96 |
Horton 96-graph |
Bondy and Murty (1976) |
REFERENCES
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 242, 1976.
Bondy, 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. "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.
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 
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." Disc. 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." Disc. Math. 1, 203-208, 1971/72.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
