Skip to main navigation Skip to search Skip to main content

Some approaches to a conjecture on short cycles in digraphs

Research output: Contribution to journalArticleAcademicpeer-review

132 Downloads (Pure)

Abstract

We consider the following special case of a conjecture due to Caccetta and Häggkvist: Let D be a digraph on n vertices that all have in-degree and out-degree at least n/3. Then, D contains a directed cycle of length 2 or 3. We discuss several necessary conditions for possible counterexamples to this conjecture, in terms of cycle structure, diameter, maximum degree, clique number, toughness, and local structure. These conditions have not enabled us to prove or refute the conjecture, but they lead to proofs of special instances of the conjecture.
Original languageEnglish
Pages (from-to)45-93
Number of pages9
JournalDiscrete applied mathematics
Volume120
Issue number1-3
DOIs
Publication statusPublished - 2002

Keywords

  • Digraph
  • Directed triangle
  • Degree condition
  • Girth

Fingerprint

Dive into the research topics of 'Some approaches to a conjecture on short cycles in digraphs'. Together they form a unique fingerprint.

Cite this