Hamiltonian degree sequences in digraphs

Details Hamiltonian degree sequences in digraphs Hamiltonian degree sequences in digraphs

2008-07-11

arxiv.org/abs/0807.1827v2

Mathematics

Combinatorics

17 pages, 2 figures. Section added which includes a proof of a conjecture of Thomassen for large tournaments. To appear in JCT

Scientific paper

We show that for each \eta>0 every digraph G of sufficiently large order n is Hamiltonian if its out- and indegree sequences d^+_1\le ... \le d^+_n and d^- _1 \le ... \le d^-_n satisfy (i) d^+_i \geq i+ \eta n or d^-_{n-i- \eta n} \geq n-i and (ii) d^-_i \geq i+ \eta n or d^+_{n-i- \eta n} \geq n-i for all i < n/2. This gives an approximate solution to a problem of Nash-Williams concerning a digraph analogue of Chv\'atal's theorem. In fact, we prove the stronger result that such digraphs G are pancyclic.

Affiliated with

Also associated with

No associations

Rating

Hamiltonian degree sequences 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 Hamiltonian degree sequences in digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hamiltonian degree sequences in digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-575912