Some approaches to a conjecture on short cycles in digraphs

Share/Save/Bookmark

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
87Kb
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
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/74713
Official URL:http://dx.doi.org/10.1016/S0166-218X(01)00279-7
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 206794