Hamiltonian Square-Paths
Hamiltonian Square-Paths
复制标题
DOI：
10.1006/jctb.1996.0039
复制
发表时间：
1996-07
期刊：
影响因子：
--
通讯作者：
G. Fan;H. Kierstead
中科院分区：
文献类型：
--
作者：
G. Fan;H. Kierstead
哈密顿平方路径（-cycle）是从哈密顿路径（cycle）中通过连接路径（cycle）中距离为2的每对顶点而获得的路径（cycle）。画一个顶点最小度为？(G)的图。Posa和Seymour推测如果？(G)？23n，它包含一个哈密顿平方环。我们证明如果？(G)?（2n?）1)/3，则包含一条哈密顿平方路径。这个结果的一个结果是Aigner和Brandt的一个定理，它证实了这个情况。(H)=2 Bollabas？埃尔德里奇猜想：如果gandhare图与（?(G)+1）（?(H)+1）？n+1，可以打包。
A hamiltonian square-path (-cycle) is one obtained from a hamiltonian path (cycle) by joining every pair of vertices of distance two in the path (cycle). LetGbe a graph onnvertices with minimum degree?(G). Posa and Seymour conjectured that if?(G)?23n, thenGcontains a hamiltonian square-cycle. We prove that if?(G)?(2n?1)/3, thenGcontains a hamiltonian square-path. A consequence of this result is a theorem of Aigner and Brandt that confirms the case?(H)=2 of the Bollabas?Eldridge Conjecture: ifGandHare graphs onnvertices and (?(G)+1)(?(H)+1)?n+1, thenGandHcan be packed.