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

DOI10.1137/20M1382398zbMATH Open1498.05064arXiv2011.11605WikidataQ114074127 ScholiaQ114074127MaRDI QIDQ5084095FDOQ5084095

Authors: Raphael M. Steiner 

Publication date: 23 June 2022

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

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.

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

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

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)

Cites Work

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

Cited In (6)

• Vertex-disjoint cycles of different lengths in local tournaments
• On the number of vertex-disjoint cycles in digraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Disjoint cycles of different lengths in graphs and digraphs
• Proof of a conjecture of Henning and yeo on vertex-disjoint directed cycles

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)