### Paper Menu >>

### Journal Menu >>

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 () M G 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 [1] and [2], for a matroid M with () M k , elements ()eEM with the property that () M ek have been characterized in terms of matroid invariants such as strength and -partitions. In this paper, we consider matroids M with ()< M k , and determine the minimum of |()||( )| E MEM , where M is a matroid that contains M as a restriction with both ()=()rM rM and () M k . This minimum is expressed as a function of certain invariants of M , 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, Fractional Arboricity 1. Introduction In this paper, we use N and Q to denote the set of all natural numbers and the set of all positive fractional numbers, respectively, and consider finite matroids and graphs. Undefined notations and terminology can be found in [5] or [6] for matroids, and [7] for graphs. Thus for a connected graph G, ()G denotes the number of components of G. For a matroid M , M r (or r, when the matroid M is understood from the context) denotes the rank function of M , and ()EM , () I M, ()CM and ()BM denote the ground set of M , and the collections of independent sets, the circuits, and the bases of M , respectively. Furthermore, if M is a ma- troid with =()EEM, and if X E, then M X is the restricted matroid of M obtained by deleting the elements in X from M , and / M X is the matroid obtained by contracting elements in X from M . As in [5] or [6], we use M e for {} M e and / M e for /{} M e. For a matroid M , let () M denote the maximum number of disjoint bases of M . For a graph G, define ()=( ())GMG , where () M G denotes the cycle ma- troid of G. Thus if G is a connected graph, then ()G is the spanning tree packing number of G. Readers are referred to [8] for a survey on ()G . The well-known spanning tree packing theorem of Nash- Williams [9] and Tutte [10] characterizes graphs with k edge-disjoint spanning trees, for any integer >0k. Edmonds [11] proved the corresponding theorem for matroids. Let >0k be an integer. For any matroid M with () M k , we are interested in finding elements ()eEM that have the property that () M ek . Characterizations of all such elements have been found in [1] and [2]. 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 [3] and Liu et al. [4], 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 () M k such that M has a restriction isomorphic to M (we then H.-J. LAI ET AL. Copyright © 2010 SciRes. AM 245 view 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 (,) F Mk 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 (,) F Mk in terms of other invariants of M . By definition, if M is a matroid with ()=0rM , then kN , () M k . 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 [9] and Tutte [10]) ()Gk if and only if () X EG , ||(( )1)Xk GX . 2) (Nash-Williams [12]) 1()aG k if and only if () X EG , ||(|( [])|( [])) X kVGX GX . Theorem 1.2 (Edmonds [11]) Let M be a matroid with ()>0rM . Each of the following holds. 1) () M k if and only if () X EM , |( )|(( )())EMX krMrX . 2) 1() M k if and only if () X EM , || () X kr X. Let M be a matroid with rank function r. For any subset () X EM with ()>0rX , the density of X is || ()= . () M M X dX rX When the matroid M is understood from the context, we often omit the subscript M . We also use ()dM for (( ))dEM. Following [13] and [14], the strength () M and the fractional arboricity () M of M are respec- tively defined as =min: <, =max:>0 . MdMXrXrM andMdXr X (1) Thus Theorem 1.2 above indicates that 1 =, =.MMandMM (2) We assume that M is a matroid with ()>0rM . A subset () X EM is an -maximal subset and | M X is an -maximal restriction if for any subset ()YEM that properly contains X , we have (|)<(|) M YMX . In [1] and [2], it has been proved that any matroid M has a unique decomposition based on its -maximal subsets. Theorem 1.3 ([1] and [2]) Let M be a matroid with ()>0rM . Then each of the following holds. 1) There exist an integer mN, and an m-tuple 12 (, ,...,) m lll of rational numbers in Q such that 12 =<<...< =, m M lllG (3) and a sequence of subsets 21 ...= (); m J JJEM (4) such that for each i with 1im , |i M J is an - maximal restriction of M with (|)= ii M Jl . 2) The integer m and the sequences (4) and (3) are uniquely determined by M . For a matroid M , the m-tuple 12 ( ,,...,) m lll 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 j J to be the set corresponding to j l. Our main result can now be stated as follows. Theorem 1.4 For kN , let M be a matroid with () M k . If ()< M k , define ()= ik J; and if () M k , let ()ik denote the smallest subscript in (3) such that ()ik lk. Then 1) () () (,)=(() ())|()| ik ik FMkkrM rJEMJ . 2) () (,)={( /)|/ |} max XEM F MkkrMXMX . In the next section, we shall present some of the useful properties related to the strength and the fractional ar- boricity of a matroid M , and to the decomposition of M . Section 3 will be devoted to the proofs of the main results. In the last section, we shall show some applica- tions of our main results. 2. Preliminaries Both () M and () M have been studied by many, see [14-16] and [17], among others. From the definition of (),()dM M and () M , we immediately have, for any matroid M with ()>0rM , ()() (). M dM M (5) A matroid M satisfying ()=() M M 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 () ={ ,,,} e e Xee e be a set such that = ee XX , ,()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 e X . Thus () ()= e eEM EM 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 {(): } e eEM XY is independent in M and ()eEM , ||1 e XY . For tN , if ()eEM , ()=et is a constant function, we write t M for M , and call t M the t-parallel extension of M . Let 1 ={ :()}()EeeEM EM . Then the bijec- tion 1 ee between ()EM and E yields a matroid isomorphism between M and | M E . Under this bijection, we shall view that =| M ME is a restric- tion of M . Theorem 2.2 (Theorem 4 of [14]) Let M be a ma- troid and let >0st be integers. Then 1) () s Mt if and only if () t M s . 2) () s Gt if and only if () t M s . Theorem 2.3 (Theorem 6 of [14]) Let M be a ma- troid. The following are equivalent. 1) ()=() M dM . 2) ()=() M dM . 3) ()=() M M . 4) ()= s Mt , for some integers >0st, and t M , the t-parallel extension of M , is a disjoint union of s bases of M . 5) ()= s Mt , for some integers >0st, and t M , the t-parallel extension of M , is a disjoint union of s bases of M . Lemma 2.4 ([14], [1] and [2]) Let M be a matroid with ()>0rM , and let 1l be fractional number. Each of the following holds. 1) (Lemma 10 [14]) If () X EM and if (|) () M XM , then (/)=() M XM . 2) (Theorem 17 of [14]) If () X EM and if ()=()dX M , then (|)= (|)=()= () M XMXdXM . 3) A matroid M is uniformly dense if and only if any subset () X EM, ()( )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 () X EM with ()>0rX such that (|) M Xl . For each rational number >1l, define =:. l SM Ml (6) Proposition 2.5 ([1] and [2]) Let >>0pq be inte- gers, and =p lQ q be a rational number. The ma- troid family l S satisfies the following properties. (C1) If ()=0rM , then l M S . (C2) If l M S and if ()eEM, then /l M eS . (C3) Let () X EM and let =|NMX. If /l M XS and if l NS , then l M S. Lemma 2.6 ([1] and [2]) Let W, ()WEM be subsets, and let lQ . If (|) M Wl and (|) M Wl , then (|( )) M WW l . Lemma 2.7 ([1] and [2 ]) If () X EM 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) () M k if and only if (,)=0FMk . 2) If () M k , then ,= .FMk krMEM Moreover, there exists a map :( )EM N , such that M is a matroid that contains M as a restrict- tion with()=()= M M k , and such that |()||( )|=(,)EMEM FMk . Proof: 1) By (2), () M k if and only if () M k . By the definition of (,) F Mk, () M k if and only if (,)=0FMk . This proves 1). 2) Since () M k , it follows by (2) that M has disjoint bases 1,, k BB such that =1 ()= k i i EM B . Define ()=|{ :}| ii eBeB . 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 == k i i ELBkrM 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 (,)=|()||()|= ()|()| F Mk 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 [18] and Lemma 2.3 of [19], among others. (For a literature review on supereulerian graphs, see [20] and [21].) Proof of Theorem 1.4 1): Let M be a matroid with ()>0rM . If () M k , then by (2) and by Theorem 1.3, 1 ()=ik i, and so () ()= ,(,)=0. ik E MJandFMk Thus Theorem 1.4 1) follows trivially with () M k . Hence we assume that ()< M k . If ()< M k , then Theorem 1.4 1) follows from Lemma 3.1. Therefore, we may assume that ()< M k and () M k . By Theorem 1.3, we must have>1m. Let H.-J. LAI ET AL. Copyright © 2010 SciRes. AM 247 ()ik be the smallest subscript in -spectrum (3) of M such that ()ik lk. By Theorem 1.3,() (|) ik M Jk . Let () =/ ik M MJ . By the assumption that ()< M k and by Lemma 2.4 1), ()=() M M . By the choice of ()ik, ()< M k , and so by Lemma 3.1, ,=||,FM kkrMEM (7) and there must be a function :( )EM N such that M satisfies ()=()=. M Mk Define : ()EM N as follows: () () =. 1 ik ik eifeJ eif eJ Then M is a matroid that contains M as a restric- tion, such that ()( ) k J MEM . By the definition of , () () |=| ikik k M JMJS . Since () /= ik k M JMS , it follows by Proposition 2.5(C3) that k M S . Thus by (7) and by Lemma 2.7, () () ,= ,= =, ik ik FMkFM kkrMEM krM rJEMJ and so Theorem 1.4 1) is established. To continue our proof for Theorem 1.4, we introduce the following function: for any () X EM, define () ,= , =,. max k kk XEM fMX krMX MX and FMfMX (8) The function (,) k f MX was introduced by Bruno and Weinberg [22] to investigate the principal partition of matroids. They are closely related to the strength and fractional arboricity of matroids, as to be shown in Lemma 3.2 below. Lemma 3.2 Let M be a matroid with ()>0rM , and let >0k be an integer. Each of the following holds. 1) ()=0 k FM if and only if () M k . 2) ()= (,) kk FMf M if and only if () M k . 3) Let ()ik denote the smallest j i in (3) such that ()ikk, and ()ik J denote the corresponding set in the -decomposition (4) of M . Then () (/ )=(,) kik F MJ FMk. 4) For any ()eEM, ()( /) kk F MFMe. In par- ticular, () (,) k F MFMk. 5) If 0() X EM satisfies0 ()=(,) kk F MfMX, then 000 ()=(/)=(/)=(/,) kkk k FMfMXFMXfMX and 0 (/) M Xk . Proof: 1) By definition (8), ()=0 k FM if and only if () X EM , (,)=(/)|(/)|0 k fMX krMXEMX. By the definition of () M , () X EM , (/)|(/)|0krM XEM X if and only if () M k . 2) By the definition of () k F M, ()= (,) kk FMf M if and only if () X EM , (( )())||()| |;krMrXEXkrME and so if and only if () X EM with ()>0rX , || () Xk rX . By the definition of () M , this happens if and only if () M k . 3) By Theorem 1.3, () (/ )< ik M Jk . By 2) of this lemma, by Lemma 2.7, and by Theorem 1.4 1), ()()() () () () =,= ==,. kik kikikik ik ik F MJfMJkrMJMJ krMrJE JFMk 4) For any ()eEM , by the definition of () k F M in (8), ()(/) kk F MFMe. It follows by 3) of this lemma that ()(,)=(,) kk F MfMXFMk. 5) By 4), and by the choice of0 X , we have 00 0 , =,= . kk k kk FMFMXf MX fMX FM Thus equalities must hold and so 000 ()=(/)=(/)=(/,) kkk k FMfMXFMXfMX ..It follows by 2) that0 (/) M Xk . This proves 5). Lemma 3.3 Suppose that 0() X EMsatisfies 0 (,)= () kk f MXF M. Then 0 (| ) M Xk . Proof: By Lemma 3.1 1), it suffices to show that 0 (| )=0 k FMX . For any 0 YX, as 00 0 000 |,= , ,= . k k f MXYkrXrYXY andfM Xk r MrXE MX It follows that 00 (|,)(, )=(,) kkk f MXY fMXfMY 0 ()=(,) kk F MfMX. Thus by definition, 0 (| ,)0 k f MXY . This implies that0 (| )=0 k FMX , and so0 (| ) M Xk . Proof of Theorem 1.4 2): By Lemma 3.2 4), it suf- fices to show that () (,) k F MFMk . We shall argue by induction on |()|EM to proceed the proof. Suppose first that ()=0 k FM . Then by Lemma 3.2 1), ()=0 k FM if and only if () M k . By Lemma 3.1 1), we have (,)=0= () k F MkF M in this case. Thus we assume that ()>0 k FM . By Lemma 3.1 1), ()>0 k FM if and only if ()< M k . If () M k , then by Lemma 3.1 2), and by Lemma 3.2 2), =,= =,. kk F MfM krMEMFMk Hence we may assume that Theorem 1.4 2) holds for smaller values of |()|EM , and that ()<<(). M kM (9) By induction, we may assume that M does not have loops. By Theorem 1.3, and by (9), both ()ik, the smal- H.-J. LAI ET AL. Copyright © 2010 SciRes. AM 248 lest j in (3) such that j lk, and ()ik J , the corre- sponding set in (4), exist. Let 0()XEM be a subset such that 0 ()=(,) kk F MfMX . By (9), 0 X . Since 0 |(/)|<|()|EM XEM, by Lemma 3.2 5) and by induction, we have 000 0 ===,, . kk k F MfMX FMX FMXk andM Xk Suppose that (,)= F Mk l. Then there exists a ma- troid M with k M S , which contains M as a res- triction and satisfies |()( )|=EM EM l . Note that 0()( ) X EM EM . Let =()()WEM EM , and 00 =() M WWclX . Then 0 ||||WW. Since k M S , it follows by Proposition 2.5 (C2) that 0 /k M XS . Since M is a restriction of M , 0 / M X is a restriction of 0 / M X . It follows by the definition of 0 (/ ,) F MXk and by (10) that 000 0 =, =,. k F MFMXkEMXEMX WWFMk This, together with Lemma 3.2 4), implies Theorem 1.4 2). 4. Applications Let G be a graph, and =() M MG be the cycle ma- troid of G. Let(,)=( (),) F GkFMGk, and (, )=((), ) kk fGX fMGX, for any edge subset X ()EG . Let ()G denote the number of connected components of G. The next theorem follows immedi- ately from Theorem 1.4. Theorem 4.1 (Theorems 3.4 and 3.10 of [4]) For kN, let G be a connected graph with (()) M Gk and let ()ik denote the smallest j i in (3) such that ()ikk. Then 1) () () (,)=(| ()|| ([])|([]) ik ik FGkk VGVGJGJ () 1) |()| ik EG J. 2) () (,)={ (,)} max XEG k F Gkf GX . The problem of reinforcing graphs to have k edge- disjoint spanning trees has also been investigated by oth- ers. In [3], the following is proved. Theorem 4.2 (Haas, Theorem 1 of [3]) The following are equivalent for a graph G, and integers >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), (()) M Gk . It follows by the assumption that |()|=(|()|1)EGk VGl and by Lemma 3.1 2) that (,)= F Gk l, and so 1) is obtained. Assume 2) holds. Since adding l edges to G can result in a graph in k S, by (1) and by (2), (()) M Gk . By Lemma 3.1 2), 1=,=,kVGEGFGk l and so 2) must hold. 5. References [1] H.-J. Lai, P. Li and Y. Liang, “Characterization of Re- movable 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 Num- ber 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 Mathe- matical 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 Ma- thematical 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 Macha- nism, 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 Frac- tional Arboricity,” Contemporary Mathematics, Vol. 89 1989, pp. 89-106. [16] 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. [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,” Jour- nal 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 Sci- ence 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. |