Some approaches to a conjecture on short cycles in digraphs

Share/Save/Bookmark

Broersma, H.J. and Li, X. (1998) Some approaches to a conjecture on short cycles in digraphs. [Report]

[img]
Preview
PDF
140Kb
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.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65668
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 141276