k-Ordered Hamilton cycles in digraphs
Copyright policy )k-Ordered Hamilton cycles in digraphs
Given a digraph D, the minimum semi-degree of D is the minimum of its minimum indegree and its minimum outdegree. D is k-ordered Hamiltonian if for every ordered sequence of k distinct vertices there is a directed Hamilton cycle which encounters these vertices in this order. Our main result is that every digraph D of sufficiently large order n with minimum semi-degree at least (n+k)/2 -1 is k-ordered Hamiltonian. The bound on the minimum semi-degree is best possible. An undirected version of this result was proved earlier by Kierstead, S��rk��zy and Selkow.
- University of Birmingham United Kingdom
- School of Mathematics University of Birmingham United Kingdom
Eulerian and Hamiltonian graphs, Hamiltonian cycle, Directed graphs (digraphs), tournaments, directed graph, Theoretical Computer Science, 05C38, Computational Theory and Mathematics, 05C20; 05C38; 05C45; 05C35, ordered cycle, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C20, Ordered cycles, Combinatorics (math.CO), 05C35, Hamilton cycles, Linkedness, Paths and cycles, 05C45, Directed graphs
Eulerian and Hamiltonian graphs, Hamiltonian cycle, Directed graphs (digraphs), tournaments, directed graph, Theoretical Computer Science, 05C38, Computational Theory and Mathematics, 05C20; 05C38; 05C45; 05C35, ordered cycle, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C20, Ordered cycles, Combinatorics (math.CO), 05C35, Hamilton cycles, Linkedness, Paths and cycles, 05C45, Directed graphs
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).5 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!