The Induced Matching Extendability On Graphs

ABSTRACTGraPhs considered in this thesis are finite, undirected and ede. ROughlyspallng, the prOPerties we are concerned in this theSis are mainly as follow:1. The degree sum conditions Of induced matching extendabe graPhs.2. Mtwal induced matching tmextendable graPhs.The orgedation of the thess is as follow'In the first chaPter, we list some notatiOnS and introduce some toPicsabout matching theory and the induced rnatching extendable gmphs. In thesecond chaPter, the degree suxn conditions of IM-extendable graPhs, IM-ex-tendable claw-free graphs and IM-extendab1e bipatite graPhs are presented. Inthe third chapter, the mbomal induced matching unextendable graphs arecharacterized.DrW Sum Conditions of 1nduced Matcbing Extendabe GraphsMgE(G) is a matching of G, if v(e) n v(f) = o for every two dis-tinct edges e, f e M. A matching is said to be the mchum .matching if itcontains the mbomum number of edges. If a matching covers all the vertices ofG, we call the matching a perfect matching of G. A matching M of G is in-duced, if E (V(M) ) = M. A graph G is induced matching extendabe (short-ly, IM-extendable), if every induced matching of G is included in a peffectmatching of G. Graph G is nextendable if G has a matching of sise n and ev-ery such matching extends to (i. e. is a subset of ) a pedect matching in G. AgraPh G is bicritical if G -- u -- v has a perfect matching for evmp chOce of two-.ponts u, v in G. Since PltnnIner[ 14 ] raised the problem of n-extendablity,-- 1 --znany resultS in the Wct M[5' 13' 14, 15 ]. Cameron gave the conCopt ofinduced matching in [2]. Ane ftmdamental resultS on induced matChing canbe found in [2, 4, 6]. In 1998, YUan[22] deW the indUced tnaching ex-tendable graphs, shothe, IM-extendable graPhs, and charaCterized them Part-ly. Plummer[12] has H the following reSul which invOlves degree stnns ofSetS of t indePendent poins, for t>3.LeUUna 1 - 1 SUPpee G is a k-connected graP with p points where p iseven and n is any inteqer sW 1t((p --2)/2+ n) + 1. Thenif(a) n = 1, G is bicritical (and hence 1 -- extendabl) and if(b) n>2, G is n-extendable.The following result is a coroary of LerIuna 1. 1 (namely, the case whent = 2).Dere1lary 1 .2 Let G be a graph with p ponts, p even, and let n be aninteger, 12, G is n-extendable.Motivated by corOllary 1. 2, we obtain the degree sum conditions of in-duced matching extendable graphs.Tbeorem 1.3 Let G be a graph with 2n vertices. If for each pair ofnonadjacent vertices u and v in G, we have d(u ) + d (v)>2rty1 -- 1, thenG is IMextendable. And this is best poSSble.Theorem 1.4 SuPpoSe that G is a claw-free gr8Ph with 2n vertices. IffOr each pair of nonadjacent vertices u and v in G, d (u ) + d (v)>2n + 3,then G is IM-extendable' And this is best mpible.-- 2 --Theorem 1 .5 Clawfree mforal planar graPh is IMextendable.In the clawfree conditiOnS, we characterize all the graPhs with twUIndegree sum 2n + 2 and 2n + 1 which are IMunextendable.Theorem 1. 6 Let G be a biPartie graPh with biPhotion (A, B ),where IA I = lBI = n - If for each pair Of nonadacent venices u and v in G,we have d (u ) + d (v )>rop1, then G is IM~extendabe.Maxhoal 1nduced Matctw U--dable GrahsA graph G is med IM-tmextendable if G is no induced matChing ex-tendabe and, for every twO nonadacent vertices x and y, G + cy is inducedmatching extendable. In chaPter 3, we charaCteri2e the mhanal IM-unextend-able graPhs.Theorem 2. 1 (Tutte's theorem) A graPh G has a perfect matching ifand ouly if for every S= V(G), o(G -- S)< I S I. Here, o(H) is the num-ber of edd componentS of H.