主題
Search

巴奈特猜想

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

巴奈特猜想斷言，每個 3-連通的二部三次平面圖都是哈密頓圖。 滿足巴奈特條件的頂點數不超過九的唯一圖是立方體圖，它確實是哈密頓圖。 截角八面體、大斜方立方八面體和大斜方二十面體的骨架也滿足這些條件，並且由於它們是阿基米德立體，因此確實是哈密頓圖。 Holton等人 (1985) 證明了所有頂點數少於 66 的圖都滿足這個猜想，但一般猜想仍然是開放的。

類似地，巴奈特猜想所有面大小至多為 6 的三次、3-連通平面圖都是哈密頓圖。 Aldred等人 (2000) 已經驗證了所有頂點數少於 177 的圖的這個猜想。

另請參閱

二部圖, 三次圖, 哈密頓圖

使用 探索

參考文獻

Aldred, R.; Bau, S.; Holton, D., and McKay, B. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM J. Disc. Math. 13, 25-32, 2000.Barnette, D. Conjecture 5 in Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, May 1968 (Ed. W. T. Tutte). New York: Academic Press, 1969.Holton, D.; Manvel, B.; and McKay, B. "Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs." J. Combin. Th. Ser. B 38, 279-297, 1985.Owens, P. J. "Bipartite Cubic Graphs and a Shortness Exponent." Disc. Math. 44, 327-330, 1983.

引用為

Weisstein, Eric W. “巴奈特猜想。” 來自 ——Wolfram 網路資源。 https://mathworld.tw/BarnettesConjecture.html

主題分類