Забыли?

?

# 241

код для вставкиСкачать
```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
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]
[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.