Some approaches to a conjecture on short cycles in digraphs


Broersma, H.J. and Li, Xueliang (2002) Some approaches to a conjecture on short cycles in digraphs. Discrete applied mathematics, 120 (1-3). pp. 45-53. ISSN 0166-218X

[img] PDF
Restricted to UT campus only
: Request a copy
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.
Item Type:Article
Copyright:© 2002 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 206794