Some approaches to a conjecture on short cycles in digraphs

Haitze J. Broersma, Xueliang Li, X. Li

Research output: Book/ReportReportProfessional

43 Downloads (Pure)

Abstract

We consider the following special case of a conjecture due to Caccetta and H\"aggkvist: 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 languageUndefined
Place of PublicationEnschede
PublisherUniversiteit Twente
Number of pages8
Publication statusPublished - 1998

Publication series

NameMemorandum Faculteit TW
PublisherDepartment of Applied Mathematics, University of Twente
No.1479
ISSN (Print)0169-2690

Keywords

  • MSC-05C20
  • MSC-05C35
  • METIS-141276
  • IR-65668
  • EWI-3299
  • MSC-05C38

Cite this