A Class Of Independent Sets Can Be Slashed By A Factor Critical Graph Degrees Conditions And An Independent Set Of Conditions

Graphs considered in this thesis are finite, undirected and simple. M(?)E(G)is a matching of G if V(e)∩V(f)=φfor any two distinct edges e and f in M.A matching M of G is a perfect matching if V(M)=V(G).A graph G is factor-critical if G-u has a perfect matching for every ver-tex u∈V(G). A subset I of V(G) is said to be independent if no two distinctvertices in I are adjacent. We say that G is independent-set-deletable-factor-critical (shortly, ID-factor-critical) if for every independent set I of G which hasthe same parity with |V(G)|, G-I has a perfect matching. If vertices u andv are connected in G, the distance between u and v in G, denoted by d_G(u, v),is the length of a shortest (u, v)-path in G. We say a graph G is of diameter rif the maximum distance between two vertices of G is r. A clique of a simplegraph G is a subset S of V(G) such that G[S] is complete. A graph G is calledclaw-free, if it does not contains K_1,3as an induced subgraph. For any set S ofvertices in G, we define the neighbor set of S in G to be the set of all verticesadjacent to vertices in S, this set is defined by N_G(S). In the matching theory,ID-factor-critical graph is a very important kind of graphs. By Gallai-EdmondsStructure Theorem, We may divide general graphs into three groups: graphswith perfect matching, bipartite graphs with positive surplus and factor-criticalgraphs. Note that an ID-factor-critical graph G with |V(G)|odd is a particularkind of factor-critical graph and an ID-factor-critical graph G with |V(G)|evenmust has a perfect matching. Then the study of ID-factor-critical graph is verymeaningful in matching theory. In this thesis, we study the degree condition ofsome ID-factor-critical graph and the problem of ID-factor-critical and claw-freegraphs of diameter 2. The main results are following: 1. Degree Condition Of ID-factor-critical GraphsTheorem 1.1 Let G be a graph with n vertices, n≥3, G(?)R,R={G|G have a clique C, |C|＜[n/3], |C| is odd and N_G(C) is an independentset}. Then if for each pair of nonadjacent vertices u and v, we have max{d(u), d(v)}≥[(2n-1)/3],then G is ID-factor-critical.2. Degree Condition Of ID-factor-critical Claw-free GraphsTheorem 2.1 Let G be a claw-free graph with n vertices, G(?)R^*, R^*={G|G have a clique C^*, |C^*| is odd and N_G(C^*) is an independent set}. Then if foreach pair of nonadjacent vertices u and v, we have max{d(u),d(v)}≥[n/2]+1(n=4m), max{d(u),d(v)}≥[n/2](n≠4m),then G is ID-factor-critical.3. ID-factor-critical and Claw-free Graphs of Diameter 2Let G be a connected Claw-free graph. Let I be an independent set ofG such that G-I is disconnected. For the convenience of explanation, writeS_ij={u_i, u_j}(?)I for 1≤i≤j≤|I|, and S_k={u_k} for some 1≤k≤|I|. Wehave these results below.Lemma 3.1 Let |I|≥4 and suppose that v₁ and v₂ are two vertices satis-fying the conditions:(1) v_i∈G_i, i=1, 2, where G_i is a component of G-I.(2) N(v₁)∩I(?)S_hj, for some h and j.(3) N(v₂)∩I(?)S_kl, for some k and l.If {h,j}={k, l} or {h, j}∩{k, l}=φ, then G is of diameter greater than 2.Theorem 3.2 If I is an independent set of a claw-free graph G of diameter2 such that G-I is disconnected, then |I|≤3. Theorem 3.3 A claw-free graph G of diameter 2 is ID-factor-critical if andonly if, for any independent set I with |I|≤3 of G, |V(G)-I|is even, then wehave G-I has no odd component.Algorithm: ID-factor-critical and claw-free graphs of diameter 2.Step 1: For each I(?)V(G) with |I|≤3, check whether I is an independent setof G such that |V(G)-I| is even or not, and simultaneously generate the set:I={I(?)V(G)|I is an independent set of G, such that |I|≤3 and |V(G)-I|is even}.Step 2: If I=φ, then stop; G is ID-factor-critical. Otherwise, go to step 3.Step 3: pick I∈I arbitrarily and form G-I.Step 4: If G-I has an odd component, then stop; G is not ID-factor-critical.Otherwise, G-I has no odd component, set I:=I\{I},go to step 2.Theorem 3.4 The algorithm we construct can determine whether a claw-free graph of diameter 2 is ID-factor-critical or not in at most O(n⁴) time.