2024/12/04 by Pierre Hoppenot, Hoppenot, Pierre, Zoltán Szigeti +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2412.03357
openalex publication_date 2024/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We deepen the link between two classic areas of combinatorial optimization: augmentation and packing arborescences. We consider the following type of questions: What is the minimum number of arcs to be added to a digraph so that in the resulting digraph there exists some special kind of packing of arborescences? We answer this question for two problems: h-regular \textsfM-independent-rooted (f,g)-bounded (α, β)-limited packing of mixed hyperarborescences and h-regular (ℓ, ℓ')-bordered (α, β)-limited packing of k hyperbranchings. We also solve the undirected counterpart of the latter, that is the augmentation problem for h-regular (ℓ, ℓ')-bordered (α, β)-limited packing of k rooted hyperforests. Our results provide a common generalization of a great number of previous results.