Linkedness and Ordered Cycles in Digraphs

DOI10.1017/S0963548307008759MaRDI QIDQ3545906zbMATHOpenAlexFDO

Authors Daniela Kühn, Deryk Osthus

Publication date 11 December 2008

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0704.0211

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Abstract: The minimum semi-degree of a digraph D is the minimum of its minimum outdegree and its minimum indegree. We show that every sufficiently large digraph D with minimum semi-degree at least n/2 +k-1 is k-linked. The bound on the minimum semi-degree is best possible and confirms a conjecture of Manoussakis from 1990. We also determine the smallest minimum semi-degree which ensures that a sufficiently large digraph D is k-ordered, i.e. that for every ordered sequence of k distinct vertices of D there is a directed cycle which encounters these vertices in this order.

Recommendations

• A minimum degree condition forcing a digraph to be k-linked
• \(k\)-Ordered Hamilton cycles in digraphs
• scientific article; zbMATH DE number 3875315
• Improved results on linkage problems
• Degree conditions for \(H\)-linked digraphs

Cites work

• About some cyclic properties in digraphs
• An extremal problem for H‐linked graphs
• An improved linear edge bound for graph linkages
• Eine Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen
• Highly connected non-2-linked digraphs
• Highly linked graphs
• Linear forests and ordered cycles
• On Minimum Degree Implying That a Graph is H‐Linked
• On Sufficient Degree Conditions for a Graph to be $k$-linked
• On \(H\)-linked graphs
• The directed subgraph homeomorphism problem
• Vertex-disjoint cycles containing specified edges
• \(k\)-linked and \(k\)-cyclic digraphs

Cited in

(8)

• Cycle index series of structures over digraphs
• \(k\)-linked and \(k\)-cyclic digraphs
• Degree conditions for \(H\)-linked digraphs
• \(k\)-Ordered Hamilton cycles in digraphs
• A minimum degree condition forcing a digraph to be k-linked
• Finding coherent cyclic orders in strong digraphs
• Links in edge-colored graphs
• Basic Terminology, Notation and Results

This page was built for publication: Linkedness and Ordered Cycles in Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3545906)