Matching Extension in the Powers of n-connected Graphs* Kara Lee Walcher DEPARTMENT OF MATHEMATICS PRESBYTERIAN COLLEGE CLINTON, SOUTH CAROLINA, USA e-mail: kwalcher@csI .presby.edu ABSTRACT Let G be a graph on p vertices. Then for a positive integer n, G is said to be n-extendible if (i) TI < p / 2 , iii) G has a set of n independent edges, and (iii)every such set is contained in a perfect matching of G. In this paper we will show that if p is even and G is TIconnected, then Gk is ([$?] - 1)-extendible for every integer k 2 2 such that [$] - 1 < p / 2 . 0 1996 John Wiley &Sons, Inc. Let G be a graph whose vertex set is V(G)and whose edge set is E(G).We will use p to stand for IV(G)l, and (throughout this paper) we will assume that G has no loops or multiple edges. Two edges are independent if they have no common endpoint, and a matching M in G is a set of (pairwise) independent edges. A matching M is a perfect matching if every vertex in G is an endpoint of one of the edges in M , and M will be called extendible if it is contained in some perfect matching in G. We will use the definition of n-extendibility as stated in Yu's 1993 paper [6]. G will be called n-extendible for a positive integer n, if (i) n < p / 2 , (ii) G has a matching of size n, and (iii) every such matching is extendible in G. A graph G will be called 0-extendible if G has a perfect matching. We will use &(u, w) to denote the length of a shortest u - path in G. If Ic is a positive integer, then Gk will denote the graph whose vertex set is V(G)and in which two vertices u and w are adjacent if and only if dc(u,w) 5 k . *This research was completed as part of a doctoral dissertation while under the supervision of Dr. David P. Sumner. Journal of Graph Theory Vol. 23, No. 4, 355-360 (1996) 0 1996 John Wiley & Sons, Inc. CCC 0364-9024/96/040355-06 356 JOURNAL OF GRAPH THEORY For a set S C: V ( G ) ,( S ) Gwill denote the subgraph induced in G by S. For simplicity we will use the notation G - S to denote the graph ( V ( G )- S)c:.finally, let JVdenote the set of positive integers, let 1.r = min{nln is an integer and n > z}, and let J1. = max{nln is an integer and n 5 x}. For any additional terminology or notation the reader is referred to Harary [I]. To begin our study of n-extendible graphs we will state two results that were published in 1980 by Michael D. Plummer [3]. These results have been used in almost every paper that has been published on the subject since their appearance. Theorem [3]. If G is connected and n-extendible for n E N , then (i) G is ( n- 1)-extendible, and (ii) G is ( n + 1)-connected. In the same paper Plummer gave an example to show that n-connectivity does not imply any extendibility condition on a graph, even if the graph has a perfect matching. Holton, Lou, and McAvaney [2] have shown that n-connectivity does, however, imply extendibility conditions on the powers (higher than one) of a graph. Theorem [2]. k 22(m - n) If p is even, G is n-connected, and 1 5 n 5 m, then G k is m-extendible for + 3. If we use part (i) of Plummer’s Theorem, then the above result may be rewritten as follows. Theorem [2]. If p is even and G is n-connected, then G” is integer k 2 2 satisfying [%$j n < p/2. + (IF] + n)-extendible for every In this paper we will strengthen this result for graphs with connectivity higher than 1. In particular, we will prove: If p is even and G is n-connected, then Gk is integer k 2 2 such that - 1< p/2. Theorem. - 1)-extendible for every We will use a result of David Sumner [4] and will use extensively Tutte’s [5] characterization of graphs that have a perfect matching and Yu‘s [6]generalization of this result. Theorem [4]. If G is a connected graph with p even, then G2 has a perfect matching. Theorem [S]. A graph G has a perfect matching if and only if for each S C V ( G )we have o(G - S ) 5 15’1,(where o(G - S ) is the number of odd components of the graph G - S). Theorem [6]. A graph G is n-extendible for 1 5 n < p / 2 if and only if for each S C V ( G ) , (i) o(G - S ) 5 IS/, and (ii) if o(G - S ) = I S 1 - 2k for some k such that 0 5 k 5 n - 1 then ( S ) Gdoes not have a matching of size k 1. + In order to prove the above theorem, we will use the following lemma: Lemma. Let N = { zl, ~ 2 , .. . , xq} for q 2 2 and let G be a graph such that for some fixed integers k 2 0 and n 2 1 we have the following: c (1) N V(G), (2) for every z # j, d ~ ( x ,xJ) , > k , and (3) for every i # j, there are at least n almost disjoint 2, - xJ paths P I ,P2,.. . , P, in G, where by “almost disjoint” we mean that for each k # 1 , Pr; n Pl C N . MATCHING EXTENSIONS 357 Then IV(G)( 2 q + n(k + (q - 2)[iJ). Proof. The proof will be by induction on q. Note that if k = 0 of if q = 2 then the result clearly holds, so assume q 2 3 and k 2 1.Let P I ,P2, . . . , P, be n almost disjoint X I - 2 2 paths in G, and let S C V ( G )be the set consisting of the first 1 vertices in each of these paths. Then by the almost disjoint property of the paths and by (2) we have: + S = {XI} { u a set of n distinct vertices that are not in N I . H e n c e , S n N = {xl),andJS/= l + n l $ ] . I Define the graph G by (loosely speaking) removing S from G and then “connecting up” any paths that become broken as a result. More precisely, let E = {abla, b E V ( G )- S and there exist q ,~ . . ,wt E S for some t E N such that a, ul, v 2 , . . . , ut, b is a path in G), 2 , . V ( G )= V(G) - S , and E ( G )= E ( G - S ) U E . Define fi = N - {xl} and note the following: fi C V ( G ) ,and for every i # j where neither i nor j is equal to 1, we still have n almost disjoint x, - xJ paths in G,where we use fi in the definition of “almost disjoint.” Thus hypotheses (1) and (3) hold for G and fi where IN1 = q - l . Claim. (2) also holds for G and fi Proof. Suppose the claim is false. Let P = xz,u1,u2,. . . ,u,, x 3 be a path in G of length 5 k. Hence m 5 k - 1. Now P cannot be a path in G, so at least one of the edges in P must be in E . Let e be an edge in P that is closest to one of the endpoints, x2 or x 3 , in P . For simplicity, let us assume that e = u,u,+1and that e is closest to 22. Then we must have i 5 171 5 [YJ which implies H = x2,u1,u2,. . . , u,is a path in G of length 5 IF]. Now u,u,+1E E , so by the definition of E there must exist w] , w 2 , . . . , w t E S for some N such that u,, wl, w 2 , . . . , w t , u,+1is a path in G. Also, 201 E S implies that there exists a w1 - z1 path I in G of length 5 [$I. But then if we start at x2 and walk along the path H to u t , cross the edge u,wl, and then walk along path I to X I ,we have an x 2 - x1 walk of length = k in G, which contradicts ( 2 ) . So the claim holds. 5 1 I Thus, by induction we have: t E [YJ+ + which implies 358 JOURNAL OF GRAPH THEORY I We are now ready to prove the theorem: Theorem. If p is even and G is n-connected, then Gk is integer k 2 2 such that - 1< p/2. 1 9 1 ([F] - 1)-extendible for every Proof. Assume the theorem is false. In other words, assume G is n-connected, k 2 2, and - 1)-extendible. By Sumner’s theorem, G2 has a perfect matching and so Gk G‘“is not (IF] must also have a perfect matching. Hence, part (ii) of Yu’s theorem must be false. Thus, there exists S C V ( G )such that o(Gk - S ) 2 IS(- 2 t for 0 5 t 5 - 2, and such that (S)Gk has a matching of size t 1. (Hence I S1 2 2 ( t l).) Let H I , H2, . . . , Hybe the components of Gk - S. Then we have: + q + 2 o(Gk - S ) 2 IS/- 2t 2 2 ( t + 1) - 2 t = 2, and which implies For each i = 1, 2, . . . ,q, define N , to be the neighborhood in G of Hi. Since G is n-connected we have (using Menger’s theorem for (iii)): (i) N, C S for every i, (ii) IN,) 2 n for every i, (iii) for every i # j , there exist n internally disjoint N, and since the components { H , }must be distance (iv) For every i # j , &(N,, N 3 )> k - - Nj paths in G, > k apart we also have: 2. Let S be the graph obtained from ( S ) Gby contracting each set N , to the point n,, where we will assume ni 6 S for each i. By the definition of S, then, it is easy to show: (v) { ~ 1 , ~ 2 , . . - 1 ~ q } C S , (vi) for every i # j , d s ( n i , n.7)> k - 2, + (vii) IS1 = /SJ- ~ ~ = l ( l N-, 1) l LI S1 - qn q , and (viii) for every i # j there exist n almost disjoint n , ~ nj paths in S, where by “almost disjoint” we mean that if PI and P2 are any two such paths then PI n P2 C { n ~7 2,2 , . . . , ny}. I Proof of (viii). We will show this for i = 1 and j = 2. By (iii) above, let P I ,P2, . . . , P, be a set of internally disjoint N1 - Nz paths in G. For each i , let K , be the graph that results from (for each j with P, n NJ # 8) contracting the set P, n NJ to the point nJ in the graph ( P L ) ~Let ;. MATCHING EXTENSIONS 359 P, be any n1 - 722 path in K,. Clearly, then, we must have P, C S for each z (otherwise some nJ would appear on P, twice), and since for every i # j , P, n PJ C N , n N,, we must have Pz n P, {nI,nz,. . . , nq). I By (v), (vi), and (viii) we have satisfied the hypotheses of the lemma. Hence c IS1 - qn + q 2 IS1 L q + n (( k - 2) + (q- 2) 1 7 1 ) , by (vii). This implies and thus e+2(--,- kn +1 ) 2 -qn+q>q+n Note that if n = 1 and k = 2 we have an immediate contradiction to inequality (0.1). Thus, we may assume n 2 2 or k 2 3, which implies that n k - n - 2 2 0. By simplifying inequality (0.2) we have - 2nk - 2n - 6 2 q ( n k - n - 2 ) 2 2 ( n k - n - 2 ) , since q 2 2. 20 This implies -6 2 -4, a contradiction. I We should note here that by using part (i) of Plummer’s result, if a graph G satisfies the hypothesesof the above theorem then Gk is m-extendible for every m such that 0 <_ m 5 1. It is natural, of course, to wonder if the theorem could be improved for some n and k . We will show here that (unless we add something to the hypotheses) the theorem cannot be “improved” by defining, for arbitrary n and k , a graph that is n-connected and such that Gk is not extendible. Let n, k E iz/ be given with k 2 2. Let m 2 k + 2 be an even integer. For each i = 2 , 3 , . . . ,m - 1,let H , be a set of n vertices. If n is odd, let HI and H , also be sets of n vertices, [%I- [?I- FIGURE 1. A 4-connected graph whose cube is not 6-extendible. 360 JOURNAL OF GRAPH THEORY + but if n is even, let H1 and H,,, be sets of n 1vertices. We will assume that the sets { H i } are pairwise disjoint. Let G be the graph formed by “linking” together H I ,H z , . . . ,H,,, via direct sums. More precisely, let V ( G )= H I U H2 U H3 U . . . U H,,,,, and let two vertices u E Hi and ‘u E H,? be adjacent in G if and only if li - j / = 1. Figure 1 illustrates G for n = 4 and k = 3. In this case, of course, = 6. We can see clearly that G is n-connected. If kn is even, let X be any perfect matching of the graph (H2UHsu.. .UH~+I)~I:. (Weknow thatsuchaperfectmatchingexistsbyusing Sumner‘s theorem since ( H 2 U H3 U . . . U H ~ + I ) <is; connected and k 2 2.) If kn is odd, let X be any perfect matching in the graph ( H 2 U H3 U . . . U Hk+l U { u } ) G k where u is any vertex in Hk+a. In either case, = Let V ( X )= { u E V ( G ) ( u is an endpoint of some edge in X } . Then, since the neighborhood of H1 in Gkis contained in V ( X ) ,the graph Gk’- V(X) has (Hl)Gkas a component, and IH1 I is odd. Thus, Gk is not [+l-extendible. 1x1 [%I. References [I] F. Harary, Graph theory, Addison-Wesley, Reading, M A ( 1969). [2] D. A. Holton D. Lou, and K. L. McAvaney, N-extendibility of line graphs, power graphs, and total graphs. Australa. J. Combznatorics 11 ( 1 995) 2 15-222. [3] M. D. Plummer, On n-extendible graphs. Discrete Math 31 (1980) 201-210. [4] D. P. Sumner, Graphs with I-factors. Proc. Amer: Math. Soc. 42 (1974) 8-12. [5] W. T. Tutte, The factorization of linear graphs. J. London Math. SOC. 22 (1947) 107-1 1 I . [6] Q. L. Yu, Characterizations of various matching extensions in graphs. Austrulasian J. of Combin. 7 (1993) 55-64. Received 5 June 1996

1/--страниц