Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity or Large Minimum Degree

DOI10.1137/20M1382398MaRDI QIDQ5084095zbMATH OpenWikidataFDO

Authors Raphael M. Steiner

Publication date 23 June 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

directed graphsstrong connectivitydegree conditionsdirected cycles

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07) Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40)

Abstract: A conjecture by Lichiardopol states that for every $kge1$ there exists an integer $g(k)$ such that every digraph of minimum out-degree at least $g(k)$ contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. Motivated by Lichiardopol's conjecture, we study the existence of vertex-disjoint directed cycles satisfying length constraints in digraphs of large connectivity or large minimum degree. Our main result is that for every $kinmathbbN$, there exists $s(k)inmathbbN$ such that every strongly $s(k)$-connected digraph contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. In contrast, for every $kinmathbbN$ we construct a strongly $k$-connected digraph containing no two vertex- or arc-disjoint directed cycles of the same length. It is an open problem whether $g(3)$ exists. Here we prove the existence of an integer $K$ such that every digraph of minimum out- and in-degree at least $K$ contains $3$ vertex-disjoint directed cycles of pairwise distinct lengths.

Recommendations

• Disjoint cycles of different lengths in graphs and digraphs
• Short disjoint cycles in graphs with degree constraints
• Short disjoint cycles in graphs with degree constraints
• Disjoint cycles with prescribed lengths and independent edges in graphs
• Minimum degree conditions for vertex-disjoint even cycles in large graphs
• Disjoint cycles in graphs with distance degree sum conditions
• Disjoint cycles in graphs with restricted independence number
• Vertex disjoint cycles of different length in digraphs
• Disjoint cycles and chorded cycles in a graph with given minimum degree
• Large vertex-disjoint cycles in a bipartite graph

Cites work

• scientific article; zbMATH DE number 3933112 (Why is no real title available?)
• An improved bound for disjoint directed cycles
• Cycles in digraphs– a survey
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• Directed tree-width
• Disjoint cycles in digraphs
• Disjoint cycles of different lengths in graphs and digraphs
• Disjoint cycles with different length in 4-arc-dominated digraphs
• Disjoint directed cycles
• Even cycles in directed graphs
• Minimum degree conditions for vertex-disjoint even cycles in large graphs
• On 3-regular digraphs of girth 4
• On 3-regular digraphs without vertex disjoint cycles of different lengths
• On vertex disjoint cycles of different lengths in 3-regular digraphs
• Proof of a conjecture of Henning and yeo on vertex-disjoint directed cycles
• Splitting digraphs
• The Directed Flat Wall Theorem
• The Even Cycle Problem for Directed Graphs
• The directed grid theorem
• Vertex disjoint cycles of different length in digraphs
• Vertex disjoint cycles of different lengths in $d$-arc-dominated digraphs
• Vertex-disjoint cycles of the same length

Cited in

(6)

• scientific article; zbMATH DE number 147644 (Why is no real title available?)
• On the number of vertex-disjoint cycles in digraphs
• Proof of a conjecture of Henning and yeo on vertex-disjoint directed cycles
• Vertex-disjoint cycles of different lengths in local tournaments
• Disjoint cycles of different lengths in graphs and digraphs
• scientific article; zbMATH DE number 842022 (Why is no real title available?)

This page was built for publication: Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity or Large Minimum Degree

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