Scientific Research

An Academic Publisher

**Reinforcing a Matroid to Have k Disjoint Bases** ()

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

Share and Cite:

H. 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.Conflicts of Interest

The authors declare no conflicts of interest.

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

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.