Edge-deletable IM-extendable graphs with minimum number of edges

Abstract: A graph is induced matching extendable, shortly IM-extendable, if every induced matching of is included in a perfect matching of . For a nonnegative integer , a graph is called a -edge-deletable IM-extendable graph, if, for every with , is IM-extendable. In this paper, we characterize the -edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer , if is a-edge-deletable IM-extendable graph on vertices, then ; furthermore, the equality holds if and only if either , or for some integer and , where is the empty graph on vertices and is the graph obtained from by replacing each vertex with a graph isomorphic to . [Copyright &y& Elsevier]