A semi-exact degree condition for Hamilton cycles in digraphs

Details A semi-exact degree condition for Hamilton cycles in digraphs A semi-exact degree condition for Hamilton cycles in digraphs

2010-02-20

arxiv.org/abs/1002.3910v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A semi-exact degree condition for Hamilton cycles in digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A semi-exact degree condition for Hamilton cycles in digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A semi-exact degree condition for Hamilton cycles in digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692813