Induced Matching Extendable Graphs With Edge-deletable Or Vertex-deletable

Matching theory is an important part of graph theory and also a active research field. It has not only many applications background, but also the source of many important ideas developed during the rapid growth of combinatorics during the last several decades.Yuan[10]introduced the problem of induced matching extendable graphs in 1998.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[10],[16],[18],[19], [22],[30],[31],[32],[33],[34],[37],[38].To further research the operation characters of IM-extendable graph,we defineκ-edge deletable IM-extendable graphs and 2κ-vertex deletable.IM-extendable graphs as following:Let G be a simple graph with|V(G)|=2n. G is called aκ-edge deletable IM-extendable graph,if for every F C E(G) with|F|=κ, G-F is IM-extendable.We say that a simple graph G is a 2k-vertex deletable IM-extendable graph,if for every S C V(G) with|5|=2κ, G-S is IM-extendable.Motivated by results on IM-extendable graphs,we obtain some results on 2k-vertex deletable IM-extendable graphs andκ-edge deletable IM-extendable graphs.In the second section of this paper,we present two sufficient conditions of 2κ-vertex deletable IM-extendable graphs,and also prove that they are all best possible. In the third section,we first characterize 4-regular 2-edge deletable IM-extendable graphs and then we further research IM-extendable graphs of n-regular(n-2)-edge deletable.