主题
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.net.cn/BarnettesConjecture.html

主题分类