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