Reinforcing the Number of Disjoint Spanning Trees

Abstract

The spanning tree packing number of a connected graph $G$, denoted by $\tau (G)$, is the maximum number of edge-disjoint spanning trees of $G$. In this paper, we determine the minimum number of edges that must be added to $G$ so that the resulting graph has spanning tree packing number at least $k$, for a given value of $k$.