1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 unknown
Given a graph G=(V,E) and a set , an orientation of G is called T-odd if precisely the vertices of T get odd in-degree. We give a good characterization for the existence of a T-odd orientation for which there exist k edge-disjoint spanning arborescences rooted at a prespecified set of k roots. Our result implies Nash-Williams' theorem on covering the edges of a graph by k forests and a (generalization of a) theorem due to Nebesky on upper embeddable graphs.
Discrete Applied Mathematics, 2001, Vol 115, Issue 1, p. 37-47