2023/10/20 by Pierre Hoppenot, Hoppenot, Pierre, Mathis Martin +3 · 1 citation
Mathematics · Biochemistry, Genetics and Molecular Biology · Computer Science · #Graph theory and applications #Protein Structure and Dynamics #Computational Drug Discovery Methods
paper · pdf · doi:10.48550/arxiv.2310.13341
The seminal papers of Edmonds \citeEgy, Nash-Williams \citeNW and Tutte \citeTu have laid the foundations of the theories of packing arborescences and packing trees. The directed version has been extensively investigated, resulting in a great number of generalizations. In contrast, the undirected version has been marginally considered. The aim of this paper is to further develop the theories of packing trees and forests. Our main result on graphs characterizes the existence of a packing of k forests, F1, …, Fk, in a graph G such that each vertex of G belongs to exactly h of the forests, and in addition, each Fi has between ℓ(i) and ℓ'(i) connected components and the total number of connected components in the packing is between α and β. Finally, we extend this result to hypergraphs and dypergraphs, the latter giving a generalization of a theorem of Bérczi and Frank \citeBF3.