主题
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 图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

三次非哈密顿图

请这样引用

Weisstein, Eric W. "三次非哈密顿图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CubicNonhamiltonianGraph.html

主题分类