Degree conditions of 2k-vertex deletable induced matching extendable claw-free 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. 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. Degree conditions of 2k-vertex deletable IM-extendable claw-free graphs are studied in this paper. The main results are as follows: (1) Let G be a claw-free graph with 2n vertices. If δ(G) ≥ 2⌈n-k/2⌉ + 2k + 1, then G is 2k-vertex deletable IM-extendable, and the result is best possible, where k is a positive integer with k ≤ n − 2. (2) Let G be a claw-free graph with 2n vertices. If for each pair of nonadjacent vertices u and v in G, d(u) + d (v) ≥ 2n + 2k + 3, then G is 2k-vertex deletable IM-extendable, and the result is best possible, where k is a positive integer with k ≤ n − 3.