Some Results About 2k Can Be Deleted And K Edges Can Be Deleted Induced Matching Extendable Graphs

Graphs considered in this paper are simple, finite, nonempty, and undirected. The problems that we are concerned in this thesis are mainly as follows:1. degree conditions of 2k-vertex deletable IM-extendable graphs.2. degree conditions of k-edge deletable IM-extendable graphs.3. the characterization of 3-regular 1-edge deletable graphs.4. the characterization of 4-regular and K₁,4— free 1-edge deletable IM-extendable graphs.Yuan [33] introduced the problem of induced matching extendable graphs. We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The IM-extendability problem has attracted many graph theorists due to its strongly theoretical interest. Some researches on IM-extendable graphs can be found, for example, in [14, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 41, 42]. To further research the operation characters of IM-extendable graph, we define k-edge deletable IM-extendable graphs and 2k-vertex deletable IM-extendable graphs as following: Let G be a simple graph with |V(G)| = 2n. G is called a k-edge deletable IM-extendable graph, if, for every F (?) E(G) with |F| = k, G - F is IM-extendable. We say that a simple graph G is a 2k-vertex deletable IM-extendable graph, if, for every S (?) V(G) with |S| = 2k, G — S is IM-extendable. A bipartite graph G with bipartition (A, B) is 2k-vertex deletable IM-extendable, if, for every S (?) V(G) with |A∩S| = |B∩S|= k, G-S is IM-extendable. Motivated by results on IM-extendable graphs, we obtain some results on 2k-vertex deletable IM-extendable graphs and k-edge deletable IM-extendable graphs.Theorem 1. Let G be a connected graph with |V(G)| = 2n and n ≥ 3. If δ(G) ≥ 4n+2k-1/3,then G is a 2k-vertex deletable IM-extendable graph, where A: is a positive integer and k < n — 1.Theorem 2. [4n+2k-1/3] is the minimum integer δ such that every graph with mini-mum degree at least 5 is a 2fc-vertex deletable IM-extendable graph, where n > 3 and fc is a positive integer with k < n — 1.Theorem 3. Let G be a bipartite graph with bipartition (A, B). If 6(G) > 2n+3fc+1, then G is a 2fc-vertex deletable IM-extendable graph, where \A\ = \B\ = n and fc is a positive integer with k < n — 1.Theorem 4. Let G be a bipartite graph with bipartition (A, B), \A\ — \B\ = n and k is a positive integer such that k < n — 1, then [2"+3fc+1] is the minimum integer S such that every bipartite graph G with minimum degree at least <5 is a 2A;-vertex deletable IM-extendable graph.Theorem 5. Let G be a connected graph with \V{G)\ = 2n. If S(G) > 2n+f+1, then G is a fc-edge deletable IM-extendable graph, where n > 3 and k is a positive integer such that [f 1 < [f J - 1.Theorem 6. Let G be a bipartite graph with bipartition (A, B) and |A| = |J3| = n. If 5(G) > 2n+3*+1, then G is a fc-edge deletable IM-extendable graph, where fc is a positive integer such that k < nf^.Theorem 7. Let G be an (n — l)-edge deletable IM-extendable graph with |V(G)| = 2n. Then g(G)=3, where n > 2.Theorem 8. The only 3-regular and 1-edge deletable IM-extendable graph is K3< 3. Theorem 9. The only 4-regular and Kit 4 — free 1-edge deletable graph is C\.