

























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 \cite{NW} and Tutte \cite{Tu} on packing spanning trees by adapting Lovász' proof \cite{Lov} of the seminal result of Edmonds \cite{Egy} on packing spanning arborescences in a digraph. Our main result on graphs extends the theorem of Katoh and Tanigawa \cite{KT} 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。