Arc-disjoint arborescences of digraphs

✍ Scribed by Cai Mao-cheng

• Publisher: John Wiley and Sons
• Year: 1983
• Tongue: English
• Weight: 182 KB
• Volume: 7
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190070213

✦ Synopsis

The purpose of this paper is to give a necessary and sufficient condition for a digraph G to contain k arcdisjoint arborescences so that the number rooted at each vertex x of G lies in some prescribed interval which depends on x.

A digraph G = (V, E) consists of a vertex set V and an arc set E such that each arc has its head and tail in V. Multiple arcs are allowed, but no loops. In this paper we consider only the finite digraphs of order 3 2 .

For X V, let x = V -X and let p ( X ) denote the number of arcs of G having their heads in X and tails in x.

An arborescence of G is defined as a spanning tree directed in such a way that each vertex of G, except one called the root of the arborescence, is the head of exactly one arc of the tree.