Disjoint cycles of different lengths in graphs and digraphs

zbMATH Open1376.05038arXiv1510.06667MaRDI QIDQ1684653FDOQ1684653

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)

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.

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

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

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

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)

Cites Work

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

Cited In (17)

• 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
• On the problem of finding disjoint cycles and dicycles in a digraph
• Vertex disjoint cycles of different lengths in $d$-arc-dominated digraphs
• Partition and disjoint cycles in digraphs
• Vertex-disjoint cycles of different lengths in multipartite tournaments
• Vertex‐disjoint cycles of the same length in tournaments
• Tournaments and Semicomplete Digraphs
• 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
• Two disjoint cycles in digraphs

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)