### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Universiteit Twente |

Number of pages | 8 |

Publication status | Published - 1998 |

### Publication series

Name | Memorandum Faculteit TW |
---|---|

Publisher | Department 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

*Some approaches to a conjecture on short cycles in digraphs*. (Memorandum Faculteit TW; No. 1479). Enschede: Universiteit Twente.

}

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

Research output: Book/Report › Report › Professional

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 -