zbMATH — the first resource for mathematics

Short cycles in digraphs with local average outdegree at least two. (English) Zbl 1023.05082
Electron. J. Comb. 10, Research paper R26, 11 p. (2003); printed version J. Comb. 10, No. 3 (2003).
Summary: Suppose \(G\) is a strongly connected digraph with order \(n\), girth \(g\) and diameter \(d\). We prove that \(d+g \leq n\) if \(G\) contains no arcs \( (u,v)\) with \(\text{deg}^+(u)=1\) and \(\text{deg}^+(v) \leq 2\). L. Caccetta and R. Häggkvist [Proc. 9th southeast Conf. on Combinatorics, graph theory, and computing, Boca Raton 1978, 181-187 (1978; Zbl 0406.05033)] showed that any digraph of order \(n\) with minimum outdegree \(2\) contains a cycle of length at most \(\lceil n/2\rceil\). Applying the above-mentioned result, we improve their result by replacing the minimum outdegree condition by some weaker conditions involving the local average outdegree. In particular, we prove that, for any digraph \(G\) of order \(n\), if either (1) \(G\) has minimum outdegree \(1\) and \(\text{deg}^+(u) + \text{deg}^+(v) \geq 4\) for all arcs \((u,v)\), or (2) \(\text{deg}^+(u) + \text{deg}^+(v) \geq 3\) for all pairs of distinct vertices \(u,v\), then \(G\) contains a cycle of length at most \(\lceil n/2\rceil\).
05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
Full Text: EMIS EuDML