Packing branchings under cardinality constraints on their root sets. (January 2021)

• Record Type: Journal Article
• Authors: Gao, Hui; Yang, Daqing
• Is Part Of: European journal of combinatorics. Volume 91(2021)
• Publication Date: 2021-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103212
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Edmonds' fundamental theorem on arborescences characterizes the existence of k pairwise arc-disjoint spanning arborescences with prescribed root sets in a digraph. In this paper, we study the problem of packing branchings in digraphs under cardinality constraints on their root sets by arborescence augmentation. Let D = ( V + x, A ) be a digraph, P = { I 1, …, I l } be a partition of [ k ], c 1, …, c l, c 1 ′, …, c l ′ be nonnegative integers such that c α ≤ c α ′ for α ∈ [ l ], F 1, …, F k be k arc-disjoint x -arborescences in D such that ∑ i ∈ I α d F i + ( x ) ≤ c α ′ for α ∈ [ l ] . We give a characterization on when F 1, …, F k can be completed to arc-disjoint spanning x -arborescences F 1 ∗, …, F k ∗ such that for any α ∈ [ l ], c α ≤ ∑ i ∈ I α d F i ∗ + ( x ) ≤ c α ′ .