Reinforcing a Matroid to Have k Disjoint Bases

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

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

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.

nullH. Lai, P. Li, Y. Liang and J. Xu, "Reinforcing a Matroid to Have k Disjoint Bases,"

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.

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