Characterization of the induced matching extendable graphs with 2n vertices and 3n edges

Abstract A graph G is induced matching extendable or IM-extendable if every induced matching of G is contained in a perfect matching of G . In 1998, Yuan proved that a connected IM-extendable graph on 2 n vertices has at least 3 n − 2 edges, and that the only IM-extendable graph with 2 n vertices and 3 n − 2 edges is T × K 2 , where T is an arbitrary tree on n vertices. In 2005, Zhou and Yuan proved that the only IM-extendable graph with 2 n ≥ 6 vertices and 3 n − 1 edges is T × K 2 + e , where T is an arbitrary tree on n vertices and e is an edge connecting two vertices that lie in different copies of T and have distance 3 between them in T × K 2 . In this paper, we introduced the definition of Q -joint graph and characterized the connected IM-extendable graphs with 2 n ≥ 4 vertices and 3 n edges.