TITLE:
On Packing Edge-Disjoint Cycles in Digraphs and Its Applications in Connectivity Problems
AUTHORS:
Vardges Melkonian
KEYWORDS:
Directed Graphs, Cycle Packing, Node Connectivity, Approximation Algorithms
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.16 No.4,
September
23,
2026
ABSTRACT: We consider the problem of packing edge-disjoint cycles in digraphs. It is shown that for
k=2,3
, any digraph with minimum degree
k
contains at least
k+1
edge-disjoint directed cycles of size
≥k
. In each of these two cases, examples are given to show that
k+1
edge-disjoint directed cycles is the best we can achieve. These results are applied to obtain approximation algorithms for
k
-node-connectivity problems.