Polyhedra with Few 3-Cuts are Hamiltonian
Polyhedra with Few 3-Cuts are Hamiltonian
复制标题
很少有 3 割的多面体是哈密顿量
DOI：
--
复制
发表时间：
2016
影响因子：
0.7
通讯作者：
C. Zamfirescu
中科院分区：
文献类型：
--
作者：
G. Brinkmann;C. Zamfirescu
1956 年，Tutte 证明每个平面 4 连通图都是哈密顿图。在本文中，我们将推广这个结果，并证明最多有 3 次 3 美元切割的多面体是哈密顿多面体。 2002 年，Jackson 和 Yu 展示了三角测量子类的这一结果。我们还证明，最多有 4 次 3 美元切割的多面体具有哈密顿路径。众所周知，对于每个 $kge，存在具有 $k$ $3$ 割的 6$ 个非哈密顿多面体。对于具有四或五个 $3$ 切割的多面体的剩余开放情况，我们给出了可能的非哈密顿多面体的下界的计算结果。
In 1956, Tutte showed that every planar 4-connected graph is hamiltonian. In this article, we will generalize this result and prove that polyhedra with at most three $3$-cuts are hamiltonian. In 2002 Jackson and Yu have shown this result for the subclass of triangulations. We also prove that polyhedra with at most four $3$-cuts have a hamiltonian path. It is well known that for each $kge 6$ non-hamiltonian polyhedra with $k$ $3$-cuts exist. We give computational results on lower bounds on the order of a possible non-hamiltonian polyhedron for the remaining open cases of polyhedra with four or five $3$-cuts.