Disjoint cycles of different lengths in graphs and digraphs

MaRDI QIDQ1684653zbMATH OpenFDO

Authors Julien Bensmail, Ararat Harutyunyan, Ngoc Khang Le, Nicolas Lichiardopol, Binlong Li

Publication date 12 December 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.06667, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p37

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

minimum degreevertex-disjoint cyclesdifferent lengths

Mathematics Subject Classification ID

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

Abstract: Understanding how the cycles of a graph or digraph behave in general has always been an important point of graph theory. In this paper, we study the question of finding a set of $k$ vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph). In the context of undirected graphs, we prove that, for every $kgeq1$, every graph with minimum degree at least $frac{k}^2+5k-22$ has $k$ vertex-disjoint cycles of different lengths, where the degree bound is best possible. We also consider stronger situations, and exhibit degree bounds (some of which are best possible) when e.g. the graph is triangle-free, or the $k$ cycles are requested to have different lengths congruent to some values modulo some $r$. In the context of directed graphs, we consider a conjecture of Lichiardopol concerning the least minimum out-degree required for a digraph to have $k$ vertex-disjoint directed cycles of different lengths. We verify this conjecture for tournaments, and, by using the probabilistic method, for regular digraphs and digraphs of small order.

Recommendations

• Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity or Large Minimum Degree
• Disjoint directed cycles
• Vertex disjoint cycles of different length in digraphs
• Two disjoint cycles in digraphs
• Proof of a conjecture of Henning and yeo on vertex-disjoint directed cycles

Cites work

• scientific article; zbMATH DE number 3150485 (Why is no real title available?)
• scientific article; zbMATH DE number 944226 (Why is no real title available?)
• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• A step toward the Bermond-Thomassen conjecture about disjoint cycles in digraphs
• Cycles in digraphs– a survey
• Cycles of even lengths modulo \(k\)
• Decomposing graphs with girth at least five under degree constraints
• Disjoint cycles in digraphs
• Disjoint directed cycles
• Graph colouring and the probabilistic method
• On decomposition of triangle-free graphs under degree constraints
• Proof of a conjecture of Henning and yeo on vertex-disjoint directed cycles
• Some Theorems on Abstract Graphs
• Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree
• Vertex disjoint cycles of different length in digraphs

Cited in

(17)

• Two disjoint cycles in digraphs
• Disjoint Chorded Cycles of the Same Length
• Disjoint cycles in tournaments and bipartite tournaments
• Vertex-disjoint cycles of different lengths in local tournaments
• Vertex-disjoint rainbow triangles in edge-colored graphs
• Tournaments and bipartite tournaments without vertex disjoint cycles of different lengths
• An improvement of Lichiardopol's theorem on disjoint cycles in tournaments
• Majority colorings of sparse digraphs
• Lichiardopol's conjecture on disjoint cycles in tournaments
• Vertex disjoint cycles of different lengths in $d$-arc-dominated digraphs
• On the problem of finding disjoint cycles and dicycles in a digraph
• Partition and disjoint cycles in digraphs
• Vertex-disjoint cycles of different lengths in multipartite tournaments
• Tournaments and Semicomplete Digraphs
• Vertex‐disjoint cycles of the same length in tournaments
• Properly colored cycles of different lengths in edge-colored complete graphs
• Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity or Large Minimum Degree

This page was built for publication: Disjoint cycles of different lengths in graphs and digraphs

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