Show simple item record

hal.structure.identifierInria Sophia Antipolis - Méditerranée [CRISAM]
dc.contributor.authorBensmail, Julien
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorHarutyunyan, Ararat
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorLe, Ngoc Khang
hal.structure.identifierDepartment of applied mathematics
dc.contributor.authorLi, Binlong
hal.structure.identifierautre
dc.contributor.authorLichiardopol, Nicolas
dc.date.accessioned2020-05-15T09:23:24Z
dc.date.available2020-05-15T09:23:24Z
dc.date.issued2017
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20743
dc.language.isoenen
dc.subjectminimum degreeen
dc.subjectvertex-disjoint cyclesen
dc.subjectdifferent lengthsen
dc.subject.ddc511en
dc.titleDisjoint cycles of different lengths in graphs and digraphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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 k≥1, every graph with minimum degree at least k2+5k−22 has~k vertex-disjoint cycles of different lengths, where the degree bound is best possible. We also consider other cases such as when the graph is triangle-free, or the k cycles are required to have different lengths modulo some value 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 some regular digraphs and digraphs of small order.en
dc.relation.isversionofjnlnameThe Electronic Journal of Combinatorics
dc.relation.isversionofjnlvol24en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2017-12
dc.relation.isversionofjnlpages4.37en
dc.relation.isversionofdoi10.37236/6921en
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-05-15T09:08:46Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record