# 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$$.
##### MSC:
 05C38 Paths and cycles 05C20 Directed graphs (digraphs), tournaments 05C35 Extremal problems in graph theory
Full Text: