Some approaches to a conjecture on short cycles in digraphs

Haitze J. Broersma, Xueliang Li, X. Li

Research output: Book/ReportReportProfessional

27 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

Broersma, H. J., Li, X., & Li, X. (1998). Some approaches to a conjecture on short cycles in digraphs. (Memorandum Faculteit TW; No. 1479). Enschede: Universiteit Twente.
Broersma, Haitze J. ; Li, Xueliang ; Li, X. / Some approaches to a conjecture on short cycles in digraphs. Enschede : Universiteit Twente, 1998. 8 p. (Memorandum Faculteit TW; 1479).
@book{60e09e440fe64f0babe80bbb907c362f,
title = "Some approaches to a conjecture on short cycles in digraphs",
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.",
keywords = "MSC-05C20, MSC-05C35, METIS-141276, IR-65668, EWI-3299, MSC-05C38",
author = "Broersma, {Haitze J.} and Xueliang Li and X. Li",
note = "Imported from MEMORANDA",
year = "1998",
language = "Undefined",
series = "Memorandum Faculteit TW",
publisher = "Universiteit Twente",
number = "1479",

}

Broersma, HJ, Li, X & Li, X 1998, Some approaches to a conjecture on short cycles in digraphs. Memorandum Faculteit TW, no. 1479, Universiteit Twente, Enschede.

Some approaches to a conjecture on short cycles in digraphs. / Broersma, Haitze J.; Li, Xueliang; Li, X.

Enschede : Universiteit Twente, 1998. 8 p. (Memorandum Faculteit TW; No. 1479).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Some approaches to a conjecture on short cycles in digraphs

AU - Broersma, Haitze J.

AU - Li, Xueliang

AU - Li, X.

N1 - Imported from MEMORANDA

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - MSC-05C20

KW - MSC-05C35

KW - METIS-141276

KW - IR-65668

KW - EWI-3299

KW - MSC-05C38

M3 - Report

T3 - Memorandum Faculteit TW

BT - Some approaches to a conjecture on short cycles in digraphs

PB - Universiteit Twente

CY - Enschede

ER -

Broersma HJ, Li X, Li X. Some approaches to a conjecture on short cycles in digraphs. Enschede: Universiteit Twente, 1998. 8 p. (Memorandum Faculteit TW; 1479).