Research ArticleOpen AccessGoogle Scholar indexed
Reinforcing a Matroid to Have k Disjoint Bases
- 1
- 2
- 3
- 4
Applied Mathematics·Volume 01 (2010)·Pages 244–249·Published 29 September 2010·DOI10.4236/am.2010.13030
Copy link · social · email
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].
KeywordsDisjoint BasesEdge-Disjoint Spanning TreesSpanning Tree Packing NumbersStrength
- 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.