主題
Search

泰特哈密頓圖猜想

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

泰特哈密頓圖猜想斷言每個立方體 多面體圖都是哈密頓圖。它由泰特於 1880 年提出，並於 1946 年被塔特用一個在 46 個頂點上的反例 (Lederberg 1965) 推翻，現在被稱為塔特圖。如果該猜想是正確的，它將暗示四色定理。

TaitsHamiltonianGraphConjecture

下表總結了一些已命名的反例，如上圖所示。 頂點數為 38 的最小例子（Barnette-Bośak-Lederberg 圖；例如，Lederberg 1965）被 Holton 和 McKay（Holton 和 McKay 1988，van Cleemput 和 Zamfirescu 2018）證明是最小的，並且顯然也由 D. Barnette 和 J. Bosák 在大約同一時間發現。

V圖參考
38Barnette-Bośak-Lederberg 圖Lederberg (1965), Thomassen (1981), Grünbaum (2003, 圖 17.1.5)
42Faulkner-Younger 圖 42Faulkner 和 Younger (1974)
42Grinberg 圖 42Faulkner 和 Younger (1974)
44Faulkner-Younger 圖 44Faulkner 和 Younger (1974)
44Grinberg 圖 44Sachs (1968), Berge (1973), Read 和 Wilson (1998, p. 274)
46Grinberg 圖 46Bondy 和 Murty (1976, p. 162)
46Tutte 圖Tutte (1972), Bondy 和 Murty (1976, p. 161)
94Thomassen 圖 94Thomassen (1981)
124124-Grünbaum 圖 124Zamfirescu (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.tw/TaitsHamiltonianGraphConjecture.html

主題分類