Packing of spanning mixed arborescences

Abstract

In this paper, we characterize a mixed graph $F$ which contains $k$ edge and arc disjoint spanning mixed arborescences $F_1,\dots ,F_k$, such that for each $v\in V(F)$, the cardinality of $\{i\in [k]:v\text{ is the root of }{F}_i\}$ lies in some prescribed interval. This generalizes both Nash-Williams and Tutte's theorem on spanning tree packing for undirected graphs and the previous characterization on digraphs which was given by Cai [in: Arc-disjoint arborescences of digraphs, J. Graph Theory 7(2) (1983), 235-240] and Frank [in: On disjoint trees and arborescences, Algebraic Methods in Graph Theory, Colloquia Mathematica Soc. J. Bolyai, Vol. 25 (North-Holland, Amsterdam) (1978), 159-169].