Common root functions of two digraphs

✍ Scribed by Cai Mao-cheng

• Publisher: John Wiley and Sons
• Year: 1989
• Tongue: English
• Weight: 265 KB
• Volume: 13
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190130211

✦ Synopsis

Let 5, and O2 be finite digraphs, both with vertex set V, let a and b be given functions from Vto Z,, and let k be a positive integer. In this paper w e give a necessary and sufficient condition for the existence of k arcdisjoint arborescences in each of D, and D2 satisfying the condition that

where r!(u) denotes the number of the arborescences in D, rooted at U ,

Let D = (V,A) be a finite digraph with vertex set V and arc set A . Multiple arcs are allowed but loops are not. For V' C V, the indegree d -( V ' ) is the number of arcs in D entering V', and 7' = V -V'.

An arborescence of D is defined as a spanning tree directed in such a way that each vertex of D, except one called the root of the arborescence, has one arc entering it.

Iffis a rational function defined on V, and V' V, we writef(V') = CUEvf(u), and set f(0) = 0. Let Z , denote the set of nonnegative integers.

A function r: V + Z , is called a root function of a digraph D = ( V , A ) if D contains r ( V ) arc-disjoint arborescences such that exactly r(u) of them are rooted at u for each u E V.