摘要
We show that for each beta > 0, every digraph G of sufficiently large order n whose out-degree and indegree sequences d(1)(+) <= ... <= d(n)(+) and d(1)(-) <= ... <= d(n)(-) satisfy d(i)(+), d(i)(-) >= min {i + beta n, n/2} is Hamiltonian. In fact, we can weaken these assumptions to (i) d(1)(+) >= min {i + beta n, n/2} or d(n-i-beta n)(-) >= n - i, (ii) d(1)(-) >= min {i + beta n, n/2} or d(n-i-beta n)(-) >= 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.
- 出版日期2010