Reinforcing a Matroid to Have k Disjoint Bases

Hong-Jian Lai, Ping Li, Yanting Liang, Jinquan Xu

.

DOI: 10.4236/am.2010.13030                

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].

Keywords

Disjoint Bases, Edge-Disjoint Spanning Trees, Spanning Tree Packing Numbers, Strength,

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	H.-J. Lai, P. Li and Y. Liang, “Characterization of Removable Elements with Respect to Having k Disjoint Bases in a Matroid,” Submitted.
[2]	P. Li, Ph.D. Dissertation, West Virginia University, to be Completed in 2012.
[3]	R. Haas, “Characterizations of Arboricity of Graphs,” Ars Combinatoria, Vol. 63, 2002, pp. 129-137.
[4]	D. Liu, H.-J. Lai and Z.-H. Chen, “Reinforcing the Number of Disjoint Spanning Trees,” Ars Combinatoria, Vol. 93, 2009, pp. 113-127.
[5]	D. J. A. Welsh, “Matroid Theory,” Academic Press, London, New York, 1976.
[6]	J. G. Oxley, “Matroid Theory,” Oxford University Press, New York, 1992.
[7]	J. A. Bondy and U. S. R. Murty, “Graph Theorym,” Springer, New York, 2008.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	W. H. Cunningham, “Optimal Attack and Reinforcement of a Network,” Journal of Associated Computer Machanism, Vol. 32, 1985, pp. 549-561.
[14]	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.
[15]	A. M. Hobbs, “Computing Edge-Toughness and Fractional Arboricity,” Contemporary Mathematics, Vol. 89 1989, pp. 89-106.
[16]	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.
[17]	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.
[18]	P. A. Catlin, “Super-Eulerian Graphscollapsible Graphs, and Four-Cycles,” Congressus Numerantium, Vol. 58, 1987, pp. 233-246.
[19]	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.
[20]	P. A. Catlin, “Super-Eulerian Graphs - A Survey,” Journal of Graph Theory, Vol. 16, No. 2, 1992, pp. 177-196.
[21]	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.
[22]	J. Bruno and L. Weinberg, “The Principal Minors of a Matroid,” Linear Algebra and Its Applications, Vol. 4, 1971, pp. 17-54.