pith. sign in

arxiv: 1002.3910 · v1 · submitted 2010-02-20 · 🧮 math.CO

A semi-exact degree condition for Hamilton cycles in digraphs

classification 🧮 math.CO
keywords cycleshamiltonhamiltoniantheoremapproximateassumptionschvatalconcerned
0
0 comments X
read the original abstract

The paper is concerned with directed versions of Posa's theorem and Chvatal's theorem on Hamilton cycles in graphs. We show that for each a>0, every digraph G of sufficiently large order n whose outdegree and indegree sequences d_1^+ \leq ... \leq d_n^+ and d_1^- \leq >... \leq d_n^- satisfy d_i^+, d_i^- \geq min{i + a n, n/2} is Hamiltonian. In fact, we can weaken these assumptions to (i) d_i^+ \geq min{i + a n, n/2} or d^-_{n - i - a n} \geq n-i; (ii) d_i^- \geq min{i + a n, n/2} or d^+_{n - i - a 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 K\"uhn, Osthus and Treglown.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.