Vertex disjoint cycles of different length in digraphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)

Abstract

Thomassen [Combinatorica, 3 (1983), pp. 393-396] proved that every digraph with minimum out-degree at least three has two vertex disjoint cycles. There are examples of 3-regular digraphs where all pairs of vertex disjoint cycles have the same length. In this paper we raise the conjectures that all 3-regular bipartite digraphs and all digraphs with minimum degree at least four have two vertex disjoint cycles of different length. We give support for our conjectures by proving that all 4-regular digraphs do indeed have two vertex disjoint cycles of different length. We furthermore discuss consequences of our results and conjectures as well as arc-weighted versions of our conjecture.

Original languageEnglish
Pages (from-to)687-694
Number of pages8
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number2
DOIs
Publication statusPublished - 2012

Keywords

  • Digraphs
  • Vertex disjoint cycles

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Vertex disjoint cycles of different length in digraphs'. Together they form a unique fingerprint.

Cite this