Packing of spanning mixed arborescences

DOI10.1002/JGT.22702MaRDI QIDQ6056788zbMATH OpenOpenAlexFDO

Authors Hui Gao, Daqing Yang

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.03218

zbMATH Keywords

treemixed graphdigraphpackingarborescence

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Combinatorial aspects of matroids and geometric lattices (05B35) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this paper, we characterize a mixed graph $F$ which contains $k$ edge and arc disjoint spanning mixed arborescences $F_1,ldots,F_k$, such that for each $vinV(F)$, the cardinality of $iin[k]:vextistherootof{F}_i$ lies in some prescribed interval. This generalizes both Nash-Williams and Tutte's theorem on spanning tree packing for undirected graphs and the previous characterization on digraphs which was given by Cai [in: Arc-disjoint arborescences of digraphs, J. Graph Theory 7(2) (1983), 235-240] and Frank [in: On disjoint trees and arborescences, Algebraic Methods in Graph Theory, Colloquia Mathematica Soc. J. Bolyai, Vol. 25 (North-Holland, Amsterdam) (1978), 159-169].

Recommendations

• On reachability mixed arborescence packing
• Packing of maximal independent mixed arborescences
• Packing of mixed hyperarborescences with flexible roots via matroid intersection
• Packing branchings under cardinality constraints on their root sets
• Reachability in arborescence packings

Cites work

• scientific article; zbMATH DE number 3799695 (Why is no real title available?)
• Arc-disjoint in-trees in directed graphs
• Arc‐disjoint arborescences of digraphs
• Connections in combinatorial optimization
• Edge-Disjoint Spanning Trees of Finite Graphs
• Matroid-Based Packing of Arborescences
• Old and new results on packing arborescences in directed hypergraphs
• On maximal independent arborescence packing
• On reachability mixed arborescence packing
• On the Problem of Decomposing a Graph into n Connected Factors
• Packing branchings under cardinality constraints on their root sets
• Packing of maximal independent mixed arborescences
• Supermodularity in unweighted graph optimization. I: Branchings and matchings

Cited in

(9)

• Matroid-Based Packing of Arborescences
• Covering a supermodular-like function in a mixed hypergraph
• On reachability mixed arborescence packing
• On arborescence packing augmentation in hypergraphs
• Packing of mixed hyperarborescences with flexible roots via matroid intersection
• Packing of maximal independent mixed arborescences
• Matroid-rooted packing of arborescences
• Packing mixed hyperarborescences
• Regular packing of rooted hyperforests with root constraints in hypergraphs

This page was built for publication: Packing of spanning mixed arborescences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6056788)