Independent arborescences in directed graphs

As a vertex-disjoint analogue of Edmonds’ arc-disjoint arborescences theorem, it was conjectured that given a directed graph D with a specified vertex r , there are k spanning arborescences rooted at r such that for every vertex v of D the k directed walks from r to v in these arborescences are internally vertex-disjoint if and only if for every vertex v of D there are k internally vertex-disjoint directed walks from r to v . Whitty (1987) [10] affirmatively settled this conjecture for k ≤ 2 , and Huck (1995) [6] constructed counterexamples for k ≥ 3 , and Huck (1999) [7] proved that the conjecture is true for every k when D is acyclic. In this paper, we generalize these results by using the concept of “convexity” which is introduced by Fujishige (2010) [4].