A Semiexact Degree Condition for Hamilton Cycles in Digraphs
A Semiexact Degree Condition for Hamilton Cycles in Digraphs
复制标题
DOI：
10.1137/090761756
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
Demetres Christofides;Peter Keevash;D. Kühn;Deryk Osthus
中科院分区：
文献类型：
--
作者：
Demetres Christofides;Peter Keevash;D. Kühn;Deryk Osthus
证明了对任意$\beta > 0$，任意阶足够大的有向图$G$n$，其出度和入度序列$d_1^+ \leq \cdots \leq d_n^+$和$d_1^- \leq \cdots \leq d_n^-$满足$di ^+，di ^- \geq \min{\{i + \beta n，n/2\}}$是Hamilton图.事实上，我们可以将这些假设弱化为（i）$d_i^+ \geq \min{\{i + \beta n，n/2\}}$或$d^-_{n-i- \beta n} \geq n-i$，（ii）$d_i^- \geq \min{\{i + \beta n，n/2\}}$或$d^+_{n-i- \beta n} \geq n-i$，并且仍然可以推导出$G$是哈密顿的。这提供了Nash-Williams在1975年提出的一个猜想的近似版本，并改进了Kuhn，Osthus，and Treglown以前的一个结果。
We show that for each $\beta > 0$, every digraph $G$ of sufficiently large order $n$ whose outdegree and indegree sequences $d_1^+ \leq \cdots \leq d_n^+$ and $d_1^- \leq \cdots \leq d_n^-$ satisfy $d_i^+, d_i^- \geq \min{\{i + \beta n, n/2\}}$ is Hamiltonian. In fact, we can weaken these assumptions to (i) $d_i^+ \geq \min{\{i + \beta n, n/2\}}$ or $d^-_{n - i - \beta n} \geq n-i$, (ii) $d_i^- \geq \min{\{i + \beta n, n/2\}}$ or $d^+_{n - i - \beta n} \geq n-i$, and still deduce that $G$ is Hamiltonian. This provides an approximate version of a conjecture of Nash-Williams from 1975 and improves a previous result of Kuhn, Osthus, and Treglown.