 Applied Mathematics, 2010, 1, 244-249 doi:10.4236/am.2010.13030 Published Online September 2010 (http://www.SciRP.org/journal/am) Copyright © 2010 SciRes. AM Reinforcing a Matroid to Have k Disjoint Bases Hong-Jian Lai1,2, Ping Li2, Yanting Liang2, Jinquan Xu3 1College of Mathematics and System Sciences, Xinjiang University, Urumqi, China 2Department of Mathematics, West Virginia University, Morgantown, USA 3Department of Mathematics, Huizhou University, Huizhou, China E-mail: hjlai@math.wvu.edu Received May 14, 2010; revised July 29, 2010; accepted August 2, 2010 Abstract Let ()M denote the maximum number of disjoint bases in a matroid M. For a connected graph G, let ()=( ())GMG, where ()MG is the cycle matroid of G. The well-known spanning tree packing theo-rem of Nash-Williams and Tutte characterizes graphs G with ()Gk. Edmonds generalizes this theorem to matroids. In  and , for a matroid M with ()Mk, elements ()eEM with the property that ()Mek have been characterized in terms of matroid invariants such as strength and -partitions. In this paper, we consider matroids M with ()0k. Edmonds  proved the corresponding theorem for matroids. Let >0k be an integer. For any matroid M with ()Mk, we are interested in finding elements ()eEM that have the property that ()Mek. Characterizations of all such elements have been found in  and . For a graph G, the problem of determin-ing which edges should be added to G so that the re-sulting graph has k edge-disjoint spanning trees has been studied, see Haas  and Liu et al. , among oth-ers. As the arguments in these papers are involved verti-ces, it is natural to consider the possibility of extending these results to matroids. Since matroids in general do not have a concept corresponding to vertices, one can no longer add an element to a matroid as adding an edge in graphs. Therefore, we need to reformulate the problem so that it would fit the matroid setting while generalizing the graph theory results. Let M be a matroid and kN. If there is a ma-troid M with ()=()rM rM and ()Mk such that M has a restriction isomorphic to M (we then H.-J. LAI ET AL. Copyright © 2010 SciRes. AM 245view M as a restriction of M), then M is a ()k-extension of M. We shall show that any ma-troid has a ()k-extension. We then define (,)FMk to be the minimum integer >0l such that M has a ()k-extension M with |()||( )|=EMEM l. The main purpose of this paper is to determine (,)FMk in terms of other invariants of M. By definition, if M is a matroid with ()=0rM , then kN , ()Mk. Accordingly, for a connected graph G, if |()|=1VG , then ()Gk for any kN. For a graph G, 1()aG, the edge arboricity of G, is the minimum number of spanning trees of G whose union equals ()EG . For a matroid, we define the similar concept 1()M, which is the minimum number of bases of M whose union equals ()EM . The fol-lowing theorems are well known. Theorem 1.1 Let G be a connected graph with |()|>1VG , and let >0k be an integer. Each of the following holds. 1) (Nash-Williams  and Tutte ) ()Gk if and only if ()XEG , ||(( )1)Xk GX. 2) (Nash-Williams ) 1()aG k if and only if ()XEG , ||(|( [])|( []))XkVGX GX. Theorem 1.2 (Edmonds ) Let M be a matroid with ()>0rM . Each of the following holds. 1) ()Mk if and only if ()XEM , |( )|(( )())EMX krMrX . 2) 1()Mk if and only if ()XEM , || ()Xkr X. Let M be a matroid with rank function r. For any subset ()XEM with ()>0rX , the density of X is ||()= .()MMXdX rX When the matroid M is understood from the context, we often omit the subscript M. We also use ()dM for (( ))dEM. Following  and , the strength ()M and the fractional arboricity ()M of M are respec-tively defined as    =min: <,=max:>0 .MdMXrXrMandMdXr X (1) Thus Theorem 1.2 above indicates that   1=, =.MMandMM   (2) We assume that M is a matroid with ()>0rM . A subset ()XEM is an -maximal subset and |MX is an -maximal restriction if for any subset ()YEM that properly contains X, we have (|)<(|)MYMX. In  and , it has been proved that any matroid M has a unique decomposition based on its -maximal subsets. Theorem 1.3 ( and ) Let M be a matroid with ()>0rM . Then each of the following holds. 1) There exist an integer mN, and an m-tuple 12(, ,...,)mlll of rational numbers in Q such that 12=<<...< =,mMlllG (3) and a sequence of subsets 21...= ();mJJJEM  (4) such that for each i with 1im , |iMJ is an - maximal restriction of M with (|)=iiMJl. 2) The integer m and the sequences (4) and (3) are uniquely determined by M. For a matroid M, the m-tuple 12( ,,...,)mlll and the sequence in (4) will be referred as the -spectrum and the -decomposition of M, respectively. For each subscript j with 1jm, we refer jJ to be the set corresponding to jl. Our main result can now be stated as follows. Theorem 1.4 For kN, let M be a matroid with ()Mk. If ()0rM , ()() ().MdM M (5) A matroid M satisfying ()=()MM is called a uniformly dense matroid. Both ()M and ()M can also be described by their behavior in some parallel ex-tension of the matroid \$M\$. Definition 2.1 Let M be a matroid and let :( )EM N be a function. For each ()eEM, let 12 ()={ ,,,}eeXee e be a set such that =eeXX, ,()ee EM with ee. The -parallel extension of M, denoted by M, is obtained from M by re-placing each element ()eEM by a class of ()e parallel elements eX. Thus ()()= eeEMEM X such that a subset ()YEM is independent in M if and H.-J. LAI ET AL. Copyright © 2010 SciRes. AM 246 only if both {(): }eeEM XY is independent in M and ()eEM , ||1eXY. For tN, if ()eEM , ()=et is a constant function, we write tM for M, and call tM the t-parallel extension of M. Let 1={ :()}()EeeEM EM . Then the bijec-tion 1ee between ()EM and E yields a matroid isomorphism between M and |ME. Under this bijection, we shall view that =|MME is a restric-tion of M. Theorem 2.2 (Theorem 4 of ) Let M be a ma-troid and let >0st be integers. Then 1) ()sMt if and only if ()tMs. 2) ()sGt if and only if ()tMs. Theorem 2.3 (Theorem 6 of ) Let M be a ma-troid. The following are equivalent. 1) ()=()MdM. 2) ()=()MdM. 3) ()=()MM. 4) ()=sMt, for some integers >0st, and tM, the t-parallel extension of M, is a disjoint union of s bases of M. 5) ()=sMt, for some integers >0st, and tM, the t-parallel extension of M, is a disjoint union of s bases of M. Lemma 2.4 (,  and ) Let M be a matroid with ()>0rM , and let 1l be fractional number. Each of the following holds. 1) (Lemma 10 ) If ()XEM and if (|) ()MXM, then (/)=()MXM. 2) (Theorem 17 of ) If ()XEM and if ()=()dX M, then (|)= (|)=()= ()MXMXdXM. 3) A matroid M is uniformly dense if and only if any subset ()XEM, ()( )dX M. 4) A matroid M is uniformly dense if and only if for any restriction N of M, ()( )NM. 5) If ()dM l, then there exists a subset ()XEM with ()>0rX such that (|)MXl. For each rational number >1l, define =:.lSM Ml (6) Proposition 2.5 ( and ) Let >>0pq be inte-gers, and =plQq be a rational number. The ma- troid family lS satisfies the following properties. (C1) If ()=0rM , then lMS. (C2) If lMS and if ()eEM, then /lMeS. (C3) Let ()XEM and let =|NMX. If /lMXS and if lNS, then lMS. Lemma 2.6 ( and ) Let W, ()WEM be subsets, and let lQ. If (|)MWl and (|)MWl, then (|( ))MWW l. Lemma 2.7 ( and [2 ]) If ()XEM is an - maximal subset, then X is a closed set in M. 3. Characterization of the Must-Added Elements with Respect to Having k Disjoint Bases The main purpose of this section is to prove Theorems 1.4. We will start with a lemma. Lemma 3.1 Let M be a matroid and let >0k be an integer. Each of the following holds. 1) ()Mk if and only if (,)=0FMk . 2) If ()Mk, then ,= .FMk krMEM Moreover, there exists a map :( )EM N, such that M is a matroid that contains M as a restrict- tion with()=()=MMk, and such that |()||( )|=(,)EMEM FMk. Proof: 1) By (2), ()Mk if and only if ()Mk. By the definition of (,)FMk, ()Mk if and only if (,)=0FMk . This proves 1). 2) Since ()Mk, it follows by (2) that M has disjoint bases 1,,kBB such that =1()= kiiEM B. Define ()=|{ :}|iieBeB. Then :( )EM N. Let =LM be the -parallel extension of M. Then by Definition 2.1, M is contained in L as a restriction. Moreover, both  =1==kiiELBkrMand ()=Lk. It follows by Theorem 2.3 that ()= ()=LLk. Hence by Theorem 2.3 1) or 2), |E(L)| = k r(L) = k r(M), and so (,)=|()||()|= ()|()|FMk ELEMkrMEM. When =2k, the cycle matroid version of Lemma 3.1 has been frequently applied in the study of supereulerian graphs, see Theorem 7 of  and Lemma 2.3 of , among others. (For a literature review on supereulerian graphs, see  and .) Proof of Theorem 1.4 1): Let M be a matroid with ()>0rM . If ()Mk, then by (2) and by Theorem 1.3, 1()=ik i, and so ()()= ,(,)=0.ikE MJandFMk Thus Theorem 1.4 1) follows trivially with ()Mk. Hence we assume that ()1m. Let H.-J. LAI ET AL. Copyright © 2010 SciRes. AM 247()ik be the smallest subscript in -spectrum (3) of M such that ()iklk. By Theorem 1.3,()(|)ikMJk. Let ()=/ikMMJ. By the assumption that ()0rM , and let >0k be an integer. Each of the following holds. 1) ()=0kFM if and only if ()Mk. 2) ()= (,)kkFMf M if and only if ()Mk. 3) Let ()ik denote the smallest ji in (3) such that ()ikk, and ()ikJ denote the corresponding set in the -decomposition (4) of M. Then ()(/ )=(,)kikFMJ FMk. 4) For any ()eEM, ()( /)kkFMFMe. In par-ticular, () (,)kFMFMk. 5) If 0()XEM satisfies0()=(,)kkFMfMX, then 000()=(/)=(/)=(/,)kkk kFMfMXFMXfMXand 0(/)MXk. Proof: 1) By definition (8), ()=0kFM if and only if ()XEM , (,)=(/)|(/)|0kfMX krMXEMX. By the definition of ()M, ()XEM, (/)|(/)|0krM XEM X if and only if ()Mk. 2) By the definition of ()kFM, ()= (,)kkFMf M if and only if ()XEM, (( )())||()| |;krMrXEXkrME and so if and only if ()XEM with ()>0rX , ||()XkrX. By the definition of ()M, this happens if and only if ()Mk. 3) By Theorem 1.3, ()(/ )0kFM . By Lemma 3.1 1), ()>0kFM if and only if ()0k and >0l. 1) |()|=(|()|1)EGk VGl and for subgraphs H of G with at least 2 vertices, |()| (|()|1)EHk VH. 2) There exists some l edges which when added to G result in a graph that can be decomposed into k spanning trees. Proof: Assume that 1) holds. Then by 1), (())MGk. It follows by the assumption that |()|=(|()|1)EGk VGl and by Lemma 3.1 2) that (,)=FGk l, and so 1) is obtained. Assume 2) holds. Since adding l edges to G can result in a graph in kS, by (1) and by (2), (())MGk. By Lemma 3.1 2),  1=,=,kVGEGFGk l and so 2) must hold. 5. References  H.-J. Lai, P. Li and Y. Liang, “Characterization of Re-movable 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 Num-ber 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 Mathe-matical 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 Ma-thematical 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 Macha-nism, 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 Frac-tional Arboricity,” Contemporary Mathematics, Vol. 89 1989, pp. 89-106.  A. M. Hobbs, L. Kannan, H.-J. Lai and H. Y. Lai, H.-J. LAI ET AL. Copyright © 2010 SciRes. AM 249“Transforming a Graph into a 1-Balanced Graph,” Dis-crete 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,” Jour-nal 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 Sci-ence 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.