Projects per year
Abstract
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 language | English |
---|---|
Pages (from-to) | 1165-1180 |
Number of pages | 16 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 98 |
Issue number | 6 |
DOIs | |
Publication status | Published - 1 Nov 2008 |
Keywords
- Linkedness
- Directed graphs
- Hamilton cycles
- Ordered cycles
Fingerprint
Dive into the research topics of 'k-Ordered Hamilton cycles in digraphs'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Directed graphs and the regularity method
Kuhn, D. (Principal Investigator) & Osthus, D. (Co-Investigator)
Engineering & Physical Science Research Council
1/10/07 → 31/03/11
Project: Research Councils