Bounds on the Lengths of Multiple Short Directed Cycles

Source abstract

We establish a bound on the lengths of multiple distinct directed cycles in digraphs with prescribed minimum outdegree conditions. Specifically, we prove that for any $m \in \mathbb{N^*}$ and $\alpha \in (0, 1)$, every digraph $G\$ on a sufficientl number of vertices with minimum outdegree of at least $\alpha n$ contains $m\$ distinct directed cycles, each with a length of at most$\frac{1}{\alpha}+74$. More precisely, this holds for all $n \geq \frac{m-1}{\alpha^2}$. This result provides an explicit relationship between the minimum outdegree density and the existence of bounded-length cycle structures in directed graphs.