2024/12/04 by Pierre Hoppenot, Hoppenot, Pierre, Zoltán Szigeti +1
Computer Science · #Digital Image Processing Techniques #Computational Geometry and Mesh Generation #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2412.03363
The aim of this paper is to further develop the theory of packing trees in a graph. We first prove the classic result of Nash-Williams \citeNW and Tutte \citeTu on packing spanning trees by adapting Lovász' proof \citeLov of the seminal result of Edmonds \citeEgy on packing spanning arborescences in a digraph. Our main result on graphs extends the theorem of Katoh and Tanigawa \citeKT on matroid-based packing of rooted trees by characterizing the existence of such a packing satisfying the following further conditions: for every vertex v, there are a lower bound f(v) and an upper bound g(v) on the number of trees rooted at v and there are a lower bound α and an upper bound β on the total number of roots. We also answer the hypergraphic version of the problem. Furthermore, we are able to solve the augmentation version of the latter problem, where the goal is to add a minimum number of edges to have such a packing. The methods developed in this paper to solve these problems may have other applications in the future.