主題
Search

三次非哈密頓圖


NonhamiltonianCubicGraphs

三次非哈密頓圖是非哈密頓圖,同時也是三次圖。在 n=10, 12, ... 個節點上的連通三次非哈密頓圖的數量為 2, 5, 35, 219, 1666, ... (OEIS A164919)。上圖顯示了一些非 snarks 的非哈密頓連通三次圖(snarks 被排除在外,因為 snarks 必然是非平面非哈密頓的)。

TaitsHamiltonianGraphConjecture

三次非哈密頓圖因泰特哈密頓圖猜想而備受關注。上面展示的三次多面體非哈密頓圖都為這個猜想提供了反例。最小可能的三次多面體非哈密頓圖出現在 38 個節點的圖上(Barnette-Bosák-Lederberg 圖),並且對於每個偶數 n >=38 都存在一個 n>=38 個節點的三次多面體非哈密頓圖 (Holton and McKay 1988, van Cleemput and Zamfirescu 2018)。

Horton 圖和 Ellingham-Horton 圖是 3-連通雙三次圖的例子,它們為塔特猜想提供了反例。

Hunter (1962) 猜想所有迴圈 5-連通多面體圖都包含哈密頓環 (Grünbaum 2003, p. 365),但 Walther (1965) 的一個 162 頂點圖提供了反例 (Grünbaum (2003, pp. 365-366)。

不可追蹤的不可追蹤三次多面體圖的最小可能大小在 54 (Knorr 2010) 和 88 (Zamfierescu 1980) 之間,並且已知對於每個偶數 n>=88 >=88 都存在這樣的圖 (van Cleemput and Zamfirescu 2018)。


另請參閱

Barnette-Bosák-Lederberg 圖, 雙三次非哈密頓圖, 三次圖, Horton 圖, 非哈密頓圖, 四次非哈密頓圖, 五次非哈密頓圖, Snark, 泰特哈密頓圖猜想, 塔特猜想, Walther 圖

使用 探索

參考文獻

Aldred, R. E. L.; Bau, S.; Holton, D. A.; and McKay, B. D. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM J. Disc. Math. 13, 25-32, 2000.Grünbaum, B. Convex Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Holton, D. A. and McKay, B. D. "The Smallest Non-Hamiltonian 3-Connected Cubic Planar Graphs Have 38 Vertices." J. Combin. Th. SeR. B 45, 305-319, 1988.Hunter, H. F. On Non-Hamiltonian Maps and their Duals. Ph. D. thesis. Troy, NY: Rensselaer Polytechnic Institute, 1962.Knorr, P. Aufspannende Kreise und Wege in polytopalen Graphen. PhD thesis. Dortmund, Germany: Universität Dortmund, 2010.Sloane, N. J. A. Sequence A164919, in "The On-Line Encyclopedia of Integer Sequences."van Cleemput, N. and Zamfirescu, C. T. "Regular Non-Hamiltonian Polyhedral Graphs." Appl. Math. Comput. 338 192-206, 2018.Walther, H. "Ein kubischer, planarer, zyklisch fünffach zusammenhängender Graf, der keinen Hamiltonkreis besizt." Wiss. Z. Hochschule Elektrotech. Ilmenau 11, 163-166, 1965.Zamfirescu, T. "Three Small Cubic Graphs with Interesting Hamiltonian Properties." J. Graph Th. 4, 287-292, 1980.

在 中被引用

三次非哈密頓圖

請這樣引用

Weisstein, Eric W. "三次非哈密頓圖。" 來自 Web 資源。 https://mathworld.tw/CubicNonhamiltonianGraph.html

主題分類