论文标题
在随机增强图中的哈密顿周期的高力量
High powers of Hamiltonian cycles in randomly augmented graphs
论文作者
论文摘要
我们研究了最小程度较大的图表中哈密顿周期的力量的存在，以随机的方式添加了一些其他边缘。对于所有整数，$ k \ geq1 $，$ r \ geq 0 $和$ \ ell \ geq（r+1）r $，对于任何$α> \ frac {k+1} $，我们显示添加$ o（n^{2-2-2/\ ell \ ell}）$ n $ n $ n $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g。概率接近一个，存在$（k \ ell+r）$的存在 - 哈密顿周期的第三功率。特别是，对于$ r = 1 $和$ \ ell = 2 $，这意味着将$ o（n）$随机边缘添加到这样的图形$ g $已经确保了$（2k+1）$ - 汉密尔顿周期的power（由Nenadov和Trujić证明是独立的）。在这种情况下，对于$ k $，$ \ ell $和$ r $的其他几种选择，我们可以证明我们的结果在渐近上是最佳的。
We investigate the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. For all integers $k\geq1$, $r\geq 0$, and $\ell\geq (r+1)r$, and for any $α>\frac{k}{k+1}$ we show that adding $O(n^{2-2/\ell})$ random edges to an $n$-vertex graph $G$ with minimum degree at least $αn$ yields, with probability close to one, the existence of the $(k\ell+r)$-th power of a Hamiltonian cycle. In particular, for $r=1$ and $\ell=2$ this implies that adding $O(n)$ random edges to such a graph $G$ already ensures the $(2k+1)$-st power of a Hamiltonian cycle (proved independently by Nenadov and Trujić). In this instance and for several other choices of $k$, $\ell$, and $r$ we can show that our result is asymptotically optimal.
