2022/02/01 by Ahmad Abdi, Gérard Cornuéjols, Abdi, Ahmad +3 · 1 citation
Computer Science · Engineering · Mathematics · #05-XX #05B35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Control (math.OC) #Primary: 90-XX #graph theory and CDMA systems #secondary: 90C57
paper · doi:10.48550/arxiv.2202.00392
openalex publication_date 2022/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let D=(V,A) be a digraph. A dicut is a cut δ+(U)⊆ A for some nonempty proper vertex subset U such that δ-(U)=∅, 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 (τ-1)-dijoin where τ denotes the smallest size of a dicut. Woodall conjectured the stronger statement that A can be partitioned into τ dijoins. Let w∈ ℤA≥ 0 and suppose every dicut has weight at least τ, for some integer τ≥ 2. Let ρ(τ,D,w):=\frac1τ∑v∈ V mv, where each mv is the integer in \0,1,…,τ-1\ equal to w(δ+(v))-w(δ-(v)) mod τ. We prove the following results: (i) If ρ(τ,D,w)∈ \0,1\, then there is an equitable w-weighted packing of dijoins of size τ. (ii) If ρ(τ,D,w)= 2, then there is a w-weighted packing of dijoins of size τ. (iii) If ρ(τ,D,w)=3, τ=3, and w=\bf 1, then A can be partitioned into three dijoins. Each result is best possible: (i) does not hold for ρ(τ,D,w)=2 even if w=\1, (ii) does not hold for ρ(τ,D,w)=3, and (iii) do not hold for general w.