Paths, cycles, and arc‐connectivity in digraphs
Xiang‐Ying Su · Journal of Graph Theory · 1995
Abstract In this paper we prove the following theorem: Let D be a k‐arcconnected digraph (multiple arcs allowed). If x is a vertex of D and / is an integer with / ≤ k, then for any / disjoint arc pairs {f1, g1}, ⃛, {f1, g1}, where f1, ⃛, f1 are arcs with head at x and g1, ⃛, g1 are arcs with tail at x, there exist in D / arc‐disjoint cycles C1, ⃛, C1 such that {fi, gi} ⊆ E(Ci) for each i (E(Ci) denotes the arc set of Ci) and such that D ‐ ∪ E(Ci) is (k ‐ 1)‐arc‐connected. Several interesting results are deduced from this theorem. Our results generalize the early works of Mader (“On a Property of n‐Edge‐Connected Digraphs,” Combinatorica, vol. 1 [1981], pp. 385‐386) and Shiloach (“Edge‐Disjoint Branching in Directed Multigraphs,” Information Processing Letters, vol. 8 [1979], pp. 24‐27). An extension of Mader's theorem about admissible liftings of digraphs is also obtained in this paper. © 1995 John Wiley & Sons, Inc.