TITLE:
Reinforcing a Matroid to Have k Disjoint Bases
AUTHORS:
Hong-Jian Lai, Ping Li, Yanting Liang, Jinquan Xu
KEYWORDS:
Disjoint Bases, Edge-Disjoint Spanning Trees, Spanning Tree Packing Numbers, Strength,
JOURNAL NAME:
Applied Mathematics,
Vol.1 No.3,
September
29,
2010
ABSTRACT: Let denote the maximum number of disjoint bases in a matroid . For a connected graph , let , where is the cycle matroid of . The well-known spanning tree packing theorem of Nash-Williams and Tutte characterizes graphs with . Edmonds generalizes this theorem to matroids. In [1] and [2], for a matroid with , elements with the property that have been characterized in terms of matroid invariants such as strength and -partitions. In this paper, we consider matroids with , and determine the minimum of , where is a matroid that contains as a restriction with both and . This minimum is expressed as a function of certain invariants of , as well as a min-max formula. These are applied to imply former results of Haas [3] and of Liu et al. [4].