×

A note on Caccetta-Häggkvist conjecture. (Chinese. English summary) Zbl 1299.05146

Summary: L. Caccetta and R. Häggkvist [in: Proc. 9th Southeast. Conf. on combinatorics, graph theory, and computing, Boca Raton 1978, 181–187 (1978; Zbl 0406.05033)] made an open conjecture: any digraph on \(n\) vertices with minimum outdegree at least \(r\) contains a directed cycle of length at most \([n/r]\). We prove that if \(\alpha\geq 0.28724\), then any digraph on \(n\) vertices with minimum outdegree at least \(\alpha n\) contains a directed cycle of length at most 4.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles

Citations:

Zbl 0406.05033
PDFBibTeX XMLCite