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

AbstractA graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅Kk+2,k+2, or k=4r−2 for some integer r≥3 and G≅C5[N2r], where N2r is the empty graph on 2r vertices and C5[N2r] is the graph obtained from C5 by replacing each vertex with a graph isomorphic to N2r