Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity or Large Minimum Degree
METADATA ONLY
Loading...
Author / Producer
Date
2022-06
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
A conjecture by Lichiardopol [SIAM J. Discrete Math., 28 (2014), pp. 1618--1627] states that for every k ≥ 1 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 k ∈ N, there exists s(k) ∈ N such that every strongly s(k)-connected digraph contains k vertex-disjoint directed cycles of pairwise distinct lengths. In contrast, for every k ∈ N 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
36 (2)
Pages / Article No.
1343 - 1362
Publisher
SIAM
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
directed graphs; directed cycles; degree conditions; strong connectivity
Organisational unit
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)