Induced Matching Scalability

Graphs considered in this thesis are finite, undirected and simple. Roughly speaking, the properties we are concerned in this thesis are mainly as follows:1. Characterizations of locally isomorphic 5-regular claw-free connected IM-extendable graphs.2. The IM-extendability of unit interval graphs and cyclic graphs C2n (1, m).The organization of the thesis is as follows: In the first chapter, we list some notations and introduce some topics about matching theory and the induced matching extendable graphs, hi the second chapter, we partly characterize locally isomorphic and 5-regular claw-free connected EM-extendable. In the third chapter, the IM-extendability of unit interval graphs and cyclic graphsC2n (1, ni) are presented.Characterizations of locally isomorphic and 5-regular claw-freeconnected IM-extendable graphsM E(G) is a matching of G, if V(e) V(f) = for every two distinctedges e, f M . If a matching covers all the vertices of G, we call the matching aperfect matching of G . A matching M of G is induced, if E(V(M)) = M . Agraph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. Graph G is n -extendable if G has a matching of size n and every such matching extends to (i.e. is a subset of) a perfect matching in G . Since Plummer [19] raised the problem of n -extendability, many results in this aspect appear [6,7,8,19]. Cameron gave the concept of induced matching in [2]. Some fundamental results on induced matching can be found in [2,4,5]. In 1998, Yuan [3] defined the induced matching extendable graphs, shortly, IM-extendable graphs, and characterized them partly. Motivated by their theory, we get the following results:Theorem 1.1 Suppose that G is connected and IM-extendable. If G is locallyisomorphic to K1 K4, 5-regular and claw-free, then G is isomorphic to K5 x K2.Theorem 1.2 Suppose that G is connected and IM-extendable but is not locally 2-connected. If G is locally isomorphic, locally connected, 5-regular and claw-free,then G is isomorphic to Cn [K2 ] for n ≥ 4.The IM-extendability of unit interval graphs and cyclic graphsC2B(1,m)Let J:, J2,., Jn be n close intervals on a line. The vertex set and edge set of G are defined, respectively, byThen graph G is called a unit interval graph.We will denote by Cln(l,m) the cyclic graph with 2n vertices x1, x2, ...., x2nin which xiXj is an edge of it if either |i-j| =1 (mod In) or | i- j| =m (mod 2n).Theorem 2.1 If a unit interval graph G with | V(G) even is 3-connected, then G is strongly IM-extendable.Theorem 2.2 A 2-connected unit interval graph G with V(G) \ even isIM-extendable if and only if for a 2-vertex cut {u, v} of G, 0(G - {u, v}) = 0.Theorem 2.3 A 2-connected unit interval graph G with V(G) even is strongly IM-extendable if and only if(1) For a 2-vertex cut {u,v} of G, o(G-{w,v}) = 0 and G-{u,v} has justtwo even components G: , G2 , such that either F(G,) NG({u,v}) or(2) G has at most two distinct 2-vertex cuts. And if G has two distinct 2-vertex cuts, then they are disjoint.Theorem 2.4 C2n(1,3) for n≥4 is M-extendable.Theorem 2.5 C2a (1,n-1) for n≥3 is IM-extendable.