泰特哈密顿图猜想

泰特哈密顿图猜想断言每个立方体多面体图都是哈密顿图。它由泰特于 1880 年提出，并于 1946 年被塔特用一个在 46 个顶点上的反例 (Lederberg 1965) 推翻，现在被称为塔特图。如果该猜想是正确的，它将暗示四色定理。

下表总结了一些已命名的反例，如上图所示。顶点数为 38 的最小例子（Barnette-Bośak-Lederberg 图；例如，Lederberg 1965）被 Holton 和 McKay（Holton 和 McKay 1988，van Cleemput 和 Zamfirescu 2018）证明是最小的，并且显然也由 D. Barnette 和 J. Bosák 在大约同一时间发现。

	图	参考
38	Barnette-Bośak-Lederberg 图	Lederberg (1965), Thomassen (1981), Grünbaum (2003, 图 17.1.5)
42	Faulkner-Younger 图 42	Faulkner 和 Younger (1974)
42	Grinberg 图 42	Faulkner 和 Younger (1974)
44	Faulkner-Younger 图 44	Faulkner 和 Younger (1974)
44	Grinberg 图 44	Sachs (1968), Berge (1973), Read 和 Wilson (1998, p. 274)
46	Grinberg 图 46	Bondy 和 Murty (1976, p. 162)
46	Tutte 图	Tutte (1972), Bondy 和 Murty (1976, p. 161)
94	Thomassen 图 94	Thomassen (1981)
124	124-Grünbaum 图 124	Zamfirescu (1976)

另请参阅

Barnette-Bośak-Lederberg 图, 连通图, 立方图, 四色定理, 图顶点, Grinberg 图, 哈密顿环, 哈密顿图, Tutte 猜想, Tutte 片段, Tutte 图

使用探索

更多尝试

参考资料

Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.Bondy, J. A. 和 Murty, U. S. R. 图 9.27 in Graph Theory with Applications. New York: North Holland, 1976.Faulkner, G. B. 和 Younger, D. H. "Non-Hamiltonian Cubic Planar Maps." Discr. Math. 7, 67-74, 1974.Grünbaum, B. 图 17.1.5 in Convex Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Holton, D. A. 和 McKay, B. D. "The Smallest Non-Hamiltonian 3-Connected Cubic Planar Graphs Have 38 Vertices." J. Combin. Th. SeR. B 45, 305-319, 1988.Honsberger, R. Mathematical Gems I. Washington, DC: Math. Assoc. Amer., pp. 82-89, 1973.Lederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf.Pegg, E. Jr. "The Icosian Game, Revisited." Mathematica J. 310-314, 11, 2009.Read, R. C. 和 Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 和 274, 1998.Sachs, H. "Ein von Kozyrev und Grinberg angegebener nicht-Hamiltonischer kubischer planarer Graph." In Beiträge zur Graphentheorie. pp. 127-130, 1968.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 198, 1990.Tait, P. G. "Remarks on the Colouring of Maps." Proc. Royal Soc. Edinburgh 10, 729, 1880.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb. Th. B 30, 36-44, 1981.Tutte, W. T. "On Hamiltonian Circuits." J. London Math. Soc. 21, 98-101, 1946.Tutte, W. T. "Non-Hamiltonian Planar Maps." In Graph Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 295-301, 1972.van Cleemput, N. 和 Zamfirescu, C. T. "Regular Non-Hamiltonian Polyhedral Graphs." Appl. Math. Comput. 338 192-206, 2018.Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.

引用为

Weisstein, Eric W. “泰特哈密顿图猜想。” 来自 ——Wolfram 网络资源。 https://mathworld.net.cn/TaitsHamiltonianGraphConjecture.html

泰特哈密顿图猜想

另请参阅

使用 探索

参考资料

引用为

主题分类

使用探索