Characterization of removable elements with respect to having kk disjoint bases in a matroid

The well-known spanning tree packing theorem of Nash-Williams and Tutte characterizes graphs with kk edge-disjoint spanning trees. Edmonds generalizes this theorem to matroids with kk disjoint bases. For any graph GG that may not have kk-edge-disjoint spanning trees, the problem of determining what edges should be added to GG so that the resulting graph has kk edge-disjoint spanning trees has been studied by Haas (2002) [11] and Liu et al. (2009) [17], among others. This paper aims to determine, for a matroid MM that has kk disjoint bases, the set Ek(M)Ek(M) of elements in MM such that for any e∈Ek(M)e∈Ek(M), M−eM−e also has kk disjoint bases. Using the matroid strength defined by Catlin et al. (1992) [4], we present a characterization of Ek(M)Ek(M) in terms of the strength of MM. Consequently, this yields a characterization of edge sets Ek(G)Ek(G) in a graph GG with at least kk edge-disjoint spanning trees such that ∀e∈Ek(G)∀e∈Ek(G), G−eG−e also has kk edge-disjoint spanning trees. Polynomial algorithms are also discussed for identifying the set Ek(M)Ek(M) in a matroid MM, or the edge subset Ek(G)Ek(G) for a connected graph GG.