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  and , 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  and of Liu et al. .
Cite this paper
nullH. Lai, P. Li, Y. Liang and J. Xu, "Reinforcing a Matroid to Have k Disjoint Bases," Applied Mathematics, Vol. 1 No. 3, 2010, pp. 244-249. doi: 10.4236/am.2010.13030.
 H.-J. Lai, P. Li and Y. Liang, “Characterization of Removable Elements with Respect to Having k Disjoint Bases in a Matroid,” Submitted.
P. Li, Ph.D. Dissertation, West Virginia University, to be Completed in 2012.
R. Haas, “Characterizations of Arboricity of Graphs,” Ars Combinatoria, Vol. 63, 2002, pp. 129-137.
D. Liu, H.-J. Lai and Z.-H. Chen, “Reinforcing the Number of Disjoint Spanning Trees,” Ars Combinatoria, Vol. 93, 2009, pp. 113-127.
D. J. A. Welsh, “Matroid Theory,” Academic Press, London, New York, 1976.
J. G. Oxley, “Matroid Theory,” Oxford University Press, New York, 1992.
J. A. Bondy and U. S. R. Murty, “Graph Theorym,” Springer, New York, 2008.
E. M. Palmer, “On the Spannig Tree Packing Number of a Graph, a Survey,” Discrete Mathematics, Vol. 230, No. 1-3, 2001, pp. 13-21.
C. St. J. A. Nash-Williams, “Edge-Disjoint Spanning Trees of Finite Graphs,” Journal of the London Mathematical Society, Vol. 36, No. 1, 1961, pp. 445-450.
W. T. Tutte, “On the Problem of Decomposing a Graph into n Connected Factors,” Journal of the London Mathematical Society, Vol. 36, No. 1, 1961, pp. 221-230.
J. Edmonds, “Lehman’s Switching Game and a Theorem of Tutte and Nash-Williams,” Journal of Research of the National Bureau of Standards, Section B, Vol. 69B, 1965, pp. 73-77.
C. St. J. A. Nash-Williams, “Decomposition of Fininte Graphs into Forest,” Journal of the London Mathematical Society, Vol. 39, No. 1, 1964, p. 12.
W. H. Cunningham, “Optimal Attack and Reinforcement of a Network,” Journal of Associated Computer Machanism, Vol. 32, 1985, pp. 549-561.
P. A. Catlin, J. W. Grossman, A. M. Hobbs and H.-J. Lai, “Fractional Arboricity, Strength and Principal Partitions in Graphs and Matroids,” Discrete Applied Mathematics, Vol. 40, No. 1, 1992, pp. 285-302.
A. M. Hobbs, “Computing Edge-Toughness and Fractional Arboricity,” Contemporary Mathematics, Vol. 89 1989, pp. 89-106.
A. M. Hobbs, L. Kannan, H.-J. Lai and H. Y. Lai, “Transforming a Graph into a 1-Balanced Graph,” Discrete Applied Mathematics, Vol. 157, No. 1, 2009, pp. 300-308.
A. M. Hobbs, L. Kannan, H.-J. Lai, H. Y. Lai and Q. W. Guo, “Balanced and 1-Balanced Graph Construction,” Discrete Applied Mathematics, Accepted.
P. A. Catlin, “Super-Eulerian Graphscollapsible Graphs, and Four-Cycles,” Congressus Numerantium, Vol. 58, 1987, pp. 233-246.
P. A. Catlin, Z. Han and H.-J. Lai, “Graphs without Spanning Closed Trails,” Discrete Mathematics, Vol. 160, No. 1-3, 1996, pp. 81-91.
P. A. Catlin, “Super-Eulerian Graphs - A Survey,” Journal of Graph Theory, Vol. 16, No. 2, 1992, pp. 177-196.
 Z. H. Chen and H.-J. Lai, “Reduction Techniques for Super-Eulerian Graphs and Related Topics - A Survey,” Combinatorics and Graph Theory 95, Vol. 1, World Science Publishing, River Edge, New York, 1995.
J. Bruno and L. Weinberg, “The Principal Minors of a Matroid,” Linear Algebra and Its Applications, Vol. 4, 1971, pp. 17-54.