4-Connected Projective-Planar Graphs Are Hamiltonian
4-Connected Projective-Planar Graphs Are Hamiltonian
复制标题
4 连通射影平面图是哈密顿图
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Xingxing Yu
中科院分区：
文献类型：
--
作者：
R. Thomas;Xingxing Yu
我们证明了标题中所述的结果（Grunbaum 的猜想）和 Plummer 的猜想：从 4 连通平面图中删除两个顶点得到的每个图都是哈密顿图。这些证明是建设性的，并产生了多项式时间算法。
We prove the result stated in the title (conjectured by Grunbaum) and a conjecture of Plummer that every graph which can be obtained from a 4-connected planar graph by deleting two vertices is Hamiltonian. The proofs are constructive and give rise to polynomial-time algorithms.