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\).