On certain Hamiltonian cycles in planar graphs
On certain Hamiltonian cycles in planar graphs
复制标题
关于平面图中的某些哈密顿循环
作者：
T. Böhme;J. Harant;M. Tkáč
在什么条件下，4连通平面图或射影平面图有一个包含某些规定边和缺失某些禁止边的哈密顿圈。应用这些结果得到了嵌入到平面中或面宽至少为5的射影平面中的5-连通图中必须存在的不同哈密顿圈的数目的新的下界。特别地，我们证明了n个顶点上不存在长度小于5的不可缩圈的5连通平面或射影平面三角剖分至少包含$2^{calO}(n^{1/4})}$不同的哈密顿圈。©1999 John Wiley&Sons，Inc.《图论》32：81-96,1999
The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least $2^{{cal O}(n^{1/4})}$ distinct Hamiltonian cycles. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 81–96, 1999