论文标题
密集图中汉密尔顿周期的兼容力量
Compatible Powers of Hamilton Cycles in Dense Graphs
论文作者
论文摘要
Krivelevich，Lee和Sudakov在1968年Kotzig研究的过渡系统概念中的动机提出了一个更一般的不兼容系统概念，以制定DIRAC图的汉密尔顿的鲁棒性。给定图形$ g =（v，e）$，一个{\ em不兼容系统} $ \ mathcal {f} $ of $ g $上的$ g $是一个家庭$ \ mathcal {f} = \ {f_v \} _ {v \ {v \ in v} $，以便在v $ in v $ f _ $ f_v $ f _ f _ f _ f _ in expect $ \ {\ {e，e'\}：e \ ne e'\在一个不兼容的系统$ \ MATHCAL {f} $是\ emph {$δ$ bounded}，如果每个顶点$ v $且每个边缘$ e $带有$ v $的事件，则最多有$Δ$对$ f_v $ in $ f_v $中，$ f_v $包含$ e $。 $ g $的子图$ h $ is \ emph {compatible}（相对于$ \ Mathcal {f} $） Krivelevich，Lee和Sudakov证明了一个通用恒定的$μ> 0 $，以至于每$μn$的不兼容系统$ \ MATHCAL {F} $在DIRAC图上都存在一个兼容的汉密尔顿周期，就可以在1988年的Häggkvistcondection and condcess and condcect and and Cycles cycect and cyc and cyccy and. $γ> 0 $和$ k \ in \ mathbb {n} $，存在一个常数$μ> 0 $，因此，对于足够大的$ n \ in \ mathbb {n} $，每个$μn$ bounded Indrapitibility在$ n $ n $ vertex $ g $ a $ n $ vertex $ g $ a $Δ（g）\ ge（\ frac {k} {k+1}+γ）n $，存在汉密尔顿周期的兼容$ k $ - $ g $。此外，我们提供了一个具有最低度$ \ frac {k+1} n+ω（n）$的结构，并且不包含汉密尔顿周期的兼容$ k $ -th功率。
Motivated by the concept of transition system investigated by Kotzig in 1968, Krivelevich, Lee and Sudakov proposed a more general notion of incompatibility system to formulate the robustness of Hamiltonicity of Dirac graphs. Given a graph $G=(V,E)$, an {\em incompatibility system} $\mathcal{F}$ over $G$ is a family $\mathcal{F}=\{F_v\}_{v\in V}$ such that for every $v\in V$, $F_v$ is a family of edge pairs in $\{\{e,e'\}: e\ne e'\in E, e\cap e'=\{v\}\}$. An incompatibility system $\mathcal{F}$ is \emph{$Δ$-bounded} if for every vertex $v$ and every edge $e$ incident with $v$, there are at most $Δ$ pairs in $F_v$ containing $e$. A subgraph $H$ of $G$ is \emph{compatible} (with respect to $\mathcal{F}$) if every pair of adjacent edges $e,e'$ of $H$ satisfies $\{e,e'\} \notin F_v$, where $v=e\cap e'$. Krivelevich, Lee and Sudakov proved that there is an universal constant $μ>0$ such that for every $μn$-bounded incompatibility system $\mathcal{F}$ over a Dirac graph, there exists a compatible Hamilton cycle, which resolves a conjecture of Häggkvist from 1988. We study high powers of Hamilton cycles in this context and show that for every $γ>0$ and $k\in\mathbb{N}$, there exists a constant $μ>0$ such that for sufficiently large $n\in\mathbb{N}$ and every $μn$-bounded incompatibility system over an $n$-vertex graph $G$ with $δ(G)\ge(\frac{k}{k+1}+γ)n$, there exists a compatible $k$-th power of a Hamilton cycle in $G$. Moreover, we give a construction which has minimum degree $\frac{k}{k+1}n+Ω(n)$ and contains no compatible $k$-th power of a Hamilton cycle.
