An Ore-Type Theorem on Hamiltonian Square Cycles
An Ore-Type Theorem on Hamiltonian Square Cycles
复制标题
哈密顿平方圈的矿石型定理
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Phong Châu
中科院分区：
文献类型：
--
作者：
Phong Châu
循环C的第k次幂是将C上距离不超过k的顶点对连接起来得到的图。循环的第二次幂称为平方循环。Pósa推测每个最小度至少为2n/3的图都包含一个哈密顿平方循环。后来，Seymour提出了一个更一般的猜想，如果G是最小度至少为(kn)/(k + 1)的图，则G包含一个哈密顿循环的k次幂。这里我们证明了Pósa猜想的一个oretype版本，如果G是一个图，其中对于所有非相邻顶点u和v， deg(u) + deg(v)≥4n/3−1/3，那么对于足够大的n， G包含一个哈密顿平方环，除非它的最小度恰好是n/3 + 2或n/3 + 5/3。这个结果的一个推论是Aigner和Brandt定理的一个ore型类比。
The kth power of a cycle C is the graph obtained from C by joining every pair of vertices with distance at most k on C. The second power of a cycle is called a square cycle. Pósa conjectured that every graph with minimum degree at least 2n/3 contains a hamiltonian square cycle. Later, Seymour proposed a more general conjecture that if G is a graph with minimum degree at least (kn)/(k + 1), then G contains the kth power of a hamiltonian cycle. Here we prove an Ore-type version of Pósa’s conjecture that if G is a graph in which deg(u) + deg(v) ≥ 4n/3 − 1/3 for all non-adjacent vertices u and v, then for sufficiently large n, G contains a hamiltonian square cycle unless its minimum degree is exactly n/3 + 2 or n/3 + 5/3. A consequence of this result is an Ore-type analogue of a theorem of Aigner and Brandt.