English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Motivated by the concept of transition system investigated by Kotzig in 1968,Krivelevich, Lee and Sudakov proposed a more general notion of incompatibilitysystem to formulate the robustness of Hamiltonicity of Dirac graphs. Given agraph $G=(V,E)$, an {\em incompatibility system} $\mathcal{F}$ over $G$ is afamily $\mathcal{F}=\{F_v\}_{v\in V}$ such that for every $v\in V$, $F_v$ is afamily of edge pairs in $\{\{e,e'\}: e\ne e'\in E, e\cap e'=\{v\}\}$. Anincompatibility system $\mathcal{F}$ is \emph{$\Delta$-bounded} if for everyvertex $v$ and every edge $e$ incident with $v$, there are at most $\Delta$pairs in $F_v$ containing $e$. A subgraph $H$ of $G$ is \emph{compatible} (withrespect 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 andSudakov proved that there is an universal constant $\mu>0$ such that for every$\mu n$-bounded incompatibility system $\mathcal{F}$ over a Dirac graph, thereexists a compatible Hamilton cycle, which resolves a conjecture ofH\"{a}ggkvist from 1988. We study high powers of Hamilton cycles in thiscontext and show that for every $\gamma>0$ and $k\in\mathbb{N}$, there exists aconstant $\mu>0$ such that for sufficiently large $n\in\mathbb{N}$ and every$\mu n$-bounded incompatibility system over an $n$-vertex graph $G$ with$\delta(G)\ge(\frac{k}{k+1}+\gamma)n$, there exists a compatible $k$-th powerof a Hamilton cycle in $G$. Moreover, we give a construction which has minimumdegree $\frac{k}{k+1}n+\Omega(n)$ and contains no compatible $k$-th power of aHamilton cycle.

Compatible Powers of Hamilton Cycles in Dense Graphs