University of Birmingham On degree sequences forcing the square of a Hamilton cycle
University of Birmingham On degree sequences forcing the square of a Hamilton cycle
复制标题
伯明翰大学论强迫汉密尔顿循环平方的度数序列
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Andrew Treglown
中科院分区：
文献类型：
--
作者：
Katherine Staden;Andrew Treglown
Pósa在1962年提出了一个著名的猜想，即任何n个顶点的最小度至少为2n/3的图都包含一个汉密尔顿圈的平方。这个猜想在1996年由Komlós，Sárközy和Szemerédi证明[27]。本文证明了Pósa猜想的一个度序列版本：给定任意η > 0，任意n阶充分大的图G包含一个汉密尔顿圈的平方，如果它的度序列d1 ≤ ·· ≤ dn满足di ≥（1/3 + η）n + i，其中i ≤ n/3.这里的度序列条件是渐近最佳可能的。我们的方法使用的正则爆破方法和连接吸收方法的混合。
A famous conjecture of Pósa from 1962 asserts that every graph on n vertices and with minimum degree at least 2n/3 contains the square of a Hamilton cycle. The conjecture was proven for large graphs in 1996 by Komlós, Sárközy and Szemerédi [27]. In this paper we prove a degree sequence version of Pósa’s conjecture: Given any η > 0, every graph G of sufficiently large order n contains the square of a Hamilton cycle if its degree sequence d1 ≤ · · · ≤ dn satisfies di ≥ (1/3 + η)n + i for all i ≤ n/3. The degree sequence condition here is asymptotically best possible. Our approach uses a hybrid of the Regularity-Blow-up method and the ConnectingAbsorbing method.
影响因子：
1.1
作者：
Peter Allen;Julia Böttcher;Hiêp Hàn;Y. Kohayakawa;Y. Person
通讯作者：
Peter Allen;Julia Böttcher;Hiêp Hàn;Y. Kohayakawa;Y. Person
DOI：
10.1137/13093827x
发表时间：
--
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
J. Böttcher;Y. Kohayakawa;A. Taraz;A. Würfl
通讯作者：
A. Würfl