k-Ordered Hamilton cycles in digraphs

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Given a digraph D. let delta(0)(D) := min{delta(+)(D), delta(-)(D)} be the minimum semi-degree of D. D is k-ordered Hamiltonian if for every sequence s(l).....s(k) of distinct vertices of D there is a directed Hamilton cycle which encounters s(l.).....s(k) in this order. Our main result is that every digraph D of sufficiently large order n with delta(0)(D) >= [(n + k)/2] - I is k-ordered Hamiltonian. The bound oil the minimum semi-degree is best possible. An undirected version of this result was proved earlier by Kierstead, Sarkozy and Selkow [H. Kierstead. G. Sarkozy. S. Selkow, On k-ordered Hamiltonian graphs, J. Graph Theory 32 (1999) 17-25]. (c) 2008 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)1165-1180
Number of pages16
JournalJournal of Combinatorial Theory. Series B
Issue number6
Publication statusPublished - 1 Nov 2008


  • Linkedness
  • Directed graphs
  • Hamilton cycles
  • Ordered cycles


Dive into the research topics of 'k-Ordered Hamilton cycles in digraphs'. Together they form a unique fingerprint.

Cite this