EXTENDABLE GRAPHS AND INDUCED SUBGRAPHS

EXTENDABLE GRAPHS AND INDUCED

       SUBGRAPHS

TsuY6sHI NISHIMURA

（Received June 17，1994） Abstract． A graph G having a 1−factor is called n−extendable ifevery matching of size n extends to a 1−factor． It is shown that if G is a connected graph of order 2p， andαand n aエe positive integers withρ一α≧n十1，such that G＼Ais n−extendable fbr any connected subgraph A of order 2α， then G is n−extendable・ AMS 1991 Mathematics 5μ句ed Classification． Primary O5C70． Keyωords andρ九τ「α8ε5． Induced subgraph， n−extendable，1−factor・   We consider only丘nite simple graphs． Let・ G be’ a graph with vertex set V（G）and edge set E（G）． For A⊂V（G），σレ1】denotes the subgraph of G induced by／l and G＼Ais the subgraph of G induced by V（G）＼ノ1・If／1 and B are disjoint subsets of V（G）， then E（A， B）denotes the set of edges with one end in、4 and the other in B． If H is a subgraph and v is a vertex， we may write E＠， H）and G＼Hinstead．of E（｛v｝，V（H））and G＼V（H）， respectivel）r． R）re∈E（G）， V（e）is the set of endvertices ofε． Further， let M be a matching （aset of independent edges）of G． V（M）denotes Ue∈M V（e）・1・et n and p be positive integers with n≦p−1and G a graph with 2p vertices having a 1−factor（aperfect matching）． Then G is said to be n−extendable if every matching of size n in G extends to a 1−factor． Further， if G has a 1−factor， we define that G is O−extendable． Other terminology on graphs can be fbund in l1］．   In［6］， Sumner proved that if every induced connected subgraph of order 2q in a connected graph G of order 2P（1＜q＜P）has a 1−factor， then G has a1−factor． This result has had a great in且uence upon some recent results fbr the existence of various factors in graphs（［2】，｛3】etc．）． Further， this result stimulates our interest in n−extendable graphs． In［4］， we proved the fbllowing七heorem． Theorem 1． Let・G・be・a c・皿nected graph・f・rder 2P（P≧3）， and let q and n be j皿tegers such砒at・1≦n＜q＜P．’SupPose f（）r some integer q， eve・’y induced co皿皿ected Subgraph・f・rder 2q is n−ex古endable． Then・G・is・n−extendable・ 129

130

_{EXTENDABLE GRAPHS AND INDUCED SUBGRAPHS}

Our purpose in this paper is to prove the following similar theorem． Main Theorem． Let G be a connected graph of order 2p． Let a and n be

positive i皿tegers suc血that p一α≧n＋1． SupP・se・that・G＼Ais n一磁endable

f・r any c・皿ected subgraph A・f・rder 2α． Then・G・is・alS・n−extendable・ We need two lemmas before proving this result．

Lemma 1（Plummer【5D．（1） lf G is n−exte皿dable， then C is（n−1）−

extendabl・．．血P繊∫・・1a・， eve・’y・set・f・k・ind・1・㎝d・nt edges（1≦k≦n）∫n G ∫scontained∫n a 1−factor of G． （ll）∬G」s c・nnected・and・n−exte皿dab1θ， the皿G」s（n＋1）−c・nnected・ We use the following elementary facts．

Lemma 2．ω1f G is a connected graph of order p（≧2）and v∈V（G）

（resp． e∈E（G））， then f・r any P・sitive・int〈）ger・q（≦P）， there・exists・a・c・皿一

nected subgraph H of G such that IHl＝qand v∈V（H）（resp・e∈E（H））・

（II） lf G（≠K2）」s a c・nnected graph with a 1−fact・r F， then f・r any P・sitive integer 2q（＜IGI）， there（exists a submatching M・f F such that IMI＝q and G【γ（M）］fs conn㏄εed・ Proof of Main Theorem． Let G， A，α， n be as in the statement of the theorem． We require two claims．   Claim 1． G＼．A is connected．

  Suppose that G＼Ais not connected fbr some co皿ected s曲graph．4． Let

O1，＿， Om（m≧2）．be the distinct components of G＼A． Then， fbr e㏄h

i（1≦i≦m），ICil is even because G＼Amust have a 1−factor from the

hypothesis． Now， there exists an edge xy∈E（C1，A）， where x∈V（01）and y∈γ（A）since G is connected． Let z（≠y）be any vertex such that z is not a cutvertex of A． Then B：＝G［（、4＼｛z｝）U｛x｝］is a connected subgraph of（］ of order 2α． If E（z， C1＼｛x｝）＝の， then since O1＼｛x｝induces a subgraph ofσ＼B that has no 1−factor， G＼Bhas also no 1−factor， which is a coqtradiction． Thus we may assume E（z，01＼｛x｝）≠0． Further， by a similar argument， fbr this z，we can easily show that E（z， Ci）≠の（2≦i≦m）． Let e∈E（Z， Ul・II＝， C，）．

Then G＼Bhas no 1−factor containing e． Thus（D＼Bis not n−extendable．

This contradicts the assumptioll of the theorem（see Fig．1）． From the proof of Claim 1， we get the following fact：．

A＼｛z｝

Fig

C1＼｛x｝ （1）EverSt vertex in A that is not a cutvertex of A mμ5‡beα輌ceη舌‡0     5・me・vertex・in（D＼A． Claim 2． If G＼Ahas fewer vertices than A， then A is（n十1）−connected．   Since．A is connected， by Lemma 2（1）， we can find a connected subgraph H of．4 sa七isfying I H I＝2p−2α． Each component of、A＼H contains a七leas七〇ne vertex which is not a cutvertex of A． By（1）， such a component has a ver七ex which is adjacent to some vertex of V（G＼A）． Thus there exists a connected

subgraph H（IHI＝ 2（p一α））of．4 such that G＼His connected． By the

hypothesis and Lemma 1（II）， H is n−extendable and（n十1）−connected．   Now we let Ho：＝Hand Ao：＝A＼H（）． For i≧0， since A is connected and since I G＼AI＜ I A I，we can choose two sets Xi⊂V（Hi）and｝Yi⊂V（Ai） satisfying （i）G［Xi U Yi］is connected and （ii）lH’1  ＞  1Xi l ≧  n十1 and lXi 1十匿1＝2（p一α）． Now， each componen七〇f、4＼（Xi U｝Yi）has a vertex which is a（lj acent to some vertex of V（G＼A）by the same reasoning as in the previous paragraph． Then G＼（Xi U yi）is also connected． Thus G［Xi U Yi］ is n−extendable and（n十1）−connected． We define Hi＋1：＝（］［Hi U Yi］and Ai＋1：ニA＼Hi＋1 if．Ai＋1≠の． If．4」＝のbut Aj＿1≠の，七hen we stop these

procedures．

  Now we show that Hi＋1（0≦i≦ゴー1）is（n十1）−connected． We use

induction on i． Suppose that Hi is（n十1）−connected． Let x and y be any two distinct vertices in V（Hi＋1）． If x and y are contained in V（Hi）（resp． V（G［Xi U｝7D）， then since Hi（resp． G［Xz U｝7D is（n十1）−connec七ed， there exist n十1internal disjoin七（x， y）−paths in Hi＋1． We let xi，x2，＿．，xn＋1 be distinct ver七ices in Xi． If x∈V（Hi）＼Xi and y∈Yi，七hen we can find an （x，xk）−path Pk （resp． （y， xk）−path Qk） （1 ≦ k ≦ n十1 ）in Hi（resp． G［Xi U Yi］）such七hat Pl＼｛x｝， P2＼｛x｝，．．．，Pn＋1＼｛x｝ （resp・ Qi＼｛y｝，

132

_{EXTENDABLE GRAPHS AND INDUCED SUBGRAPHS}

Q2＼｛y｝，．．．，Qn＋1＼｛y｝）are disjoint． Hlence， there exist n十1internal disj oint （x，y）−paths in Hi＋1． Thus， Hi＋l is（n十1）−connected by Menger’s theorem． Since耳i≡A， this completeS the proof． By（1）and Claim 2， we have the following： （2） _{ij G＼A has fewer vertices thαn A， then・ev￠ry vertex in A is ad」’acent}

鋤tl・α・t・n・励・X・ in・G＼A輌硫・μ励妙卿・吻raph・B

of A， G＼BiS C・nnected． Moreover， by Claim 1 and the hypothesis， （3） _{亙IG＼Al＜レll and B is a subgraph《）f A sαtisiVing IBI＝2（ρ一α），} ￡九εη吻ce G＼Bis connected， B・is・connected・and・n−e庇n6αble・   In the rest of this paper， we give a proof of the main part of theorem． Let

M：＝｛e1，＿，en｝⊂E（G）be an arbitrary matching of size n and let

妬妬妬

  ｛el，＿，e九｝＝E（・4， G＼・4）∩M，   ｛e九＋1，．．．，ek｝＝E（A）∩ハイ， and

：ニ｛e★＋1，．．．，eπ｝＝E（G＼・4）∩M  （1≦九≦k≦ n）・

Let ei＝xiyi∈Ml， where xi∈γ（G＼．4）and yi∈γ（A）（1≦i≦ん）． Since

G＼．A is n−extendable， by Lemma 1（II）， C＼Ahas a 1−factor F＊ which contains M3． We de丘ne three disjoint subsets of F＊ as follows： ＝ ＝ ＝

司躍躍

｛XaXb∈F． I Xa 7 Xb∈V（Ml）｝，

｛XcZc∈F． I Xc∈V（M1）and Zc∈V（G＼A）＼V（Ml）｝， and

F．＼（理u躍）．

Further， we let Z：＝V（F．2）＼y（M1）and 1） ：＝ G＼（A U V（瓦｝）UV（F．2））＝． G【V（蹄）］．Note IZI＝11田1≦lMI l≦IMl＝n． Since G＼ノ1 is（n十1）−connected， （4）

_{G＼（AUVのi8 C・nnected∫for any subset W（ヅZ．}

  qASE 1．凶≦IDI＋21M，1＋IZI．

  By（4）， since G＼（A U Z）is connected， GID U y（ハぜ1）1（＝G［V（醇U．M1）D is connected・Ifレ11≦11）1十21Mi 1， then since I G［D u v（Ml）］1＝11）1十21M111≧ レ41r2a， we can find a submatching NI of増UMI such that l NI l’＝αand

G［V（Nl）］is co皿ected by Lernnpa 2（II）． Then G＼V（N1）is n−extendable and

hence G＼γ（Nl）has a 1−factor N2 which contains（Ml＼」V1）UM2 U（M3＼

Nl）． Then」VI Uハr2 is a required 1−factor of G． We may assume Z≠ψa皿d

IDI十21MII十lzl≧IAI＞IDI十’21Mi1． By（4）， we can choose a subset

Zl of Z such that Gl：＝（D｛V（F．3 Uバグ1）UZ1］is connected and lGll＝2α． By the hypothesis of the theorem， G＼V（Gl）is connected and n−extendable． Therefbre， by． temma 1（1）；G「＼V（G1）h誌a1−factor F which cOntains M2． Since G［V（躍UMI U F）1（＝『G＼、．Z1）is connected and IG＼Zil＞ 2α， by Lemma 2（II）， there exists a subset Nl of増UMI U F satisfying INi 1＝α and G［V（Nl）］is connected． Then G＼V（ハri）is connected and n−extendable． Therefbre， G＼V（」V1）has a 1−factorハr2 which contains M＼Nl．1VI Uハr2 is a desired 1＿factor．

  CAsE 2． レll＞IDI十21Mi1十IZI・

  1・et Ao：＝・4＼γ（Ml）． In this case， since l・41＝1／101十IMi l， we have IAo l＞IDI十1Mi 1十IZi＝IG＼、41． Now， we let r and q be nonnegative integers

satisfying IAI＝lG＼．Al（r十1）十qand O≦σ＜lG＼Ai． We decompose

Ao as follows：        r

V（A。）＝（V（M2）UR・）’U（URZ）U Rr＋・，

      i＝1 where」R，；satisfies （i）  V（M…2） ∩瑠  ：：：@ Ri ∩Rゴ  ＝  の    （ 0 ≦ i ≦  ゴ ≦ 7令 十 1，  i  ≠   ゴ  ︶， （ii） 1Ro U V（M2）1＝ iRi 1＝ 2（p一α） and  l．Rr＋11＝ q （1≦i≦r）． Note that since l V（M，）1≦2n＜2（p一α），we can take Ro satisf河ng the above equality． Now we can choose，Ri satisfying E（，R（｝UV（M2），γ（M1）） ≠ のif Ml ≠ψand G＼（U書＝o Rr＋1＿i）are connected fbr allゴ （0 ≦ゴ ≦r）・ We

note that G＼（．R（）UV（M2））and G＼，Ri（1 ≦i≦r十1）are connected by

（2）．By（3）， C［，R｛）UV（M2）］has a 1−factor Fo whiρh containsハ42， and G［Ri］ has a 1−factor Fi fbr all i（1≦i≦r）． Further， since Glγ（Ml u F．3）l is connected，」τ：＝ハイ1 u増U（U；＝o Fi）induces a connected subgraph qf． G， that is， G＼（Z U Rr＋1）is connected． NOte that if Mi＝0， then since蹄＝具and レll＞IG＼Al，G［v（F．u（U：＝o Fi））】is connected by（2）・If 1島＋1uzl＜ 2（P一α），． then we can take a submatching」V1 ⊂ ．1’of size（p一α）−IRr＋1 U Zl／2 such that G＼（V（Nl）URr＋1 U Z）is co皿㏄ted by Lemma 2（1正）． Then since G［（V（Nl）∪．R，・＋1 U Z）】is connected by Claim l and n−extendable by the hypotheSis， it has a 1‘factor Fr＋1 which contains N1∩Mby Lemma 1（1）．

134

_{EXTENDABLE GRAPHS AND INDUCED SUBGRAPHS}

G＼A

G＼v（Nl）

Rr＋1 lv（M、） Fig．2 Thus G has a 1−factor（ア＼Nl）U耳＋1， which contains M（see Fig．2）． We

may assume IRr＋1 U ZI≧ 2（p一α）． Hence， Ml≠Oand Z≠の． Since

lRr＋11＜2（p一α）and IZI≦n（＜2（p一α））， then we can decompose Z into Zl and Z2 such that I品＋1UZI l＝2（p一α）． Then G［1ノ（ア）UZ21（＝Gへ（Z1∪．R，・＋1）） is connected by（4）． By the hypothesis and Claim 1， G［．R r“＋1UZ1］is connected and n−extendable． Thus this induced subgraph of G has a 1−factor耳＋1． Of course， V（∫U」Fr＋1）induces a connected subgraph of G． Thus， by Lemma 2 （II）， there exists a submatching NI of Je U Fr＋10f sizeαsuch that G［V（」V1）l is connected． By the hypothesis and Claim 1， G［Z2∪（V（アU耳＋1）＼V（1V1））］ is connected and n−extendable． Therefbre it has a 1−factor N2 which contains （（アU耳＋1）＼N1）∩M． Now， NI U∧r2 is a 1−factor of G which containsハ4． This completes the proof of the theorem．□

Re ferences

［11G．Chartrand and LLesniak， Grapんs 8 Digrαphs，2nd ed．， Wadsworth． ｛2j Y．Egawa， H Enomoto， and A．Saito， Factors and induced subgrapん5．Discrete Math．68   （1988） 179−189． ［31Y．Egawa， H．Enomoto， and A．Saito， On comρonent∫factors．Graphs and Combinat．2   （1986）223−225． ［4］T．Nishimura，、4 theorem oπη一extendαbte graphs．Ars Combinat．（to appear）． ［5］MD．Plummer， On n−extendable graphs． Discrete Math．31（1980）201−210． ［6］D．P．Sumner， Grapん8ω拗1−factors． Proc． Amer． Math． Soc．42（1974）8−12．

Tsuyoshi Nishimura Department of Mathematics

Shibaura Institute of Tecknology Fukasaku， Omiya 330， JAPAN