On Packing Dijoins in Digraphs and Weighted Digraphs

Abstract: Let

D = (V, A)

be a digraph. A dicut is a cut

d e l t a^{+} (U) s u b s e t e q A

for some nonempty proper vertex subset

U

such that

d e l t a^{-} (U) = e m p t y s e t

, a dijoin is an arc subset that intersects every dicut at least once, and more generally a

k

-dijoin is an arc subset that intersects every dicut at least

k

times. Our first result is that

A

can be partitioned into a dijoin and a

(a u - 1)

-dijoin where

a u

denotes the smallest size of a dicut. Woodall conjectured the stronger statement that

A

can be partitioned into

a u

dijoins. Let

w i n m a t h b b Z_{g e q 0}^{A}

and suppose every dicut has weight at least

a u

, for some integer

a u g e q 2

. Let

h o (a u, D, w) := f r a c 1 a u s u m_{v i n V} m_{v}

, where each

m_{v}

is the integer in

0, 1, l d o t s, a u - 1

equal to

w (d e l t a^{+} (v)) - w (d e l t a^{-} (v))

mod

a u

. We prove the following results: (i) If

h o (a u, D, w) i n 0, 1

, then there is an equitable

w

-weighted packing of dijoins of size

a u

. (ii) If

h o (a u, D, w) = 2

, then there is a

w

-weighted packing of dijoins of size

a u

. (iii) If

h o (a u, D, w) = 3

,

a u = 3

, and

, then

A

can be partitioned into three dijoins. Each result is best possible: (i) does not hold for

h o (a u, D, w) = 2

even if

w = 1

, (ii) does not hold for

h o (a u, D, w) = 3

, and (iii) do not hold for general

w

.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: On Packing Dijoins in Digraphs and Weighted Digraphs