Linkedness and Ordered Cycles in Digraphs

DOI10.1017/S0963548307008759zbMATH Open1162.05025arXiv0704.0211OpenAlexW2156630912MaRDI QIDQ3545906FDOQ3545906

Authors: Daniela Kühn, Deryk Osthus 

Publication date: 11 December 2008

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

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.

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

Recommendations

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)