Let G = (V, A) be a digraph with a root r, and suppose that each arc a of G has integers b(a) and b'(a) with b'(a)* b(a)aO. In this paper we give necessary and sufficient conditions for the existence of k r-arborescences in G such that they cover each arc a at least b(a) and at most b'(a) times and each of them contains exactly one arc leaving r. The main result of this paper contains as special cases a number of packing and covering theorems concerning arborescences.
Let G = (V, A) be a finite digraph with vertex set V and arc set A such that each arc has its tail and head in V. Parallel arcs are allowed, but loops are not. An arc with tail u and head v is denoted by (u, v).
We write 3 = V\S for S z V and V\v = V(v) for Y E V. For S E V and B GA, let D;(S) denote the set of arcs of B with their heads in S and tails in s, d;(S) = ID;(S)1 and Slf = {v ES: D;(V) rl Di(S) # 0). When B =A, these are abbreviated to D-(S), d-(S) and S*, respectively. Similarly define D:(S) and d,+(S). A vertex r E V is called a (graphical) source of G = (V, A) if d-(r) = 0. An arborescence rooted at r (briefly r-arborescence) is a spanning tree directed in such a way that each vertex TV # r has one arc entering it. We say that an arc subset B of G = (V, A) is covered by arborescences T,, * * * 9 Tk if every arc of B is in at least one K. If f is a rational function defined on A and B GA, we write f(B) = Eaeef(a), and set f(0) = 0.
Packing and covering problems concerning arborescences have been investigated by several authors, and a number of papers on this and related subjects have appeared, see for example the references at the end of this paper.
In this paper we consider a general problem of covering digraphs with arborescences, in which both lower and upper bounds are imposed on the number of covering times for each arc, and give a generalization and unification of packing and covering theorems concerning arborescences. * Work supported in part by NSFC.