Degree And Connectivity Conditions For IM-Extendibility and Vertex-Deletable IM-Extendibility

Abstract

A graph is called induced matching extendable, if every induced matching of it is contained in a perfect matching of it. A graph \(G\) is called \(2k\)-vertex deletable induced matching extendable, if \(G — S\) is induced matching extendable for every \(S \subset V(G)\) with \(|S| = 2k\). The following results are proved in this paper. (1) If \(\kappa(G) \geq \lceil \frac{v(G)}{3} \rceil +1\) and \(\max\{d(u), d(v)\} \geq \frac{2v(G)+1}{3}\) for every two nonadjacent vertices \(u\) and \(v\), then \(G\) is induced matching extendable. (2) If \(\kappa(G) \geq \lceil \frac{v(G)+4k}{3}\rceil\) and \(\max\{d(u), d(v)\} \geq \lceil \frac{2v(G)+2k}{3} \rceil\) for every two nonadjacent vertices \(u\) and \(v\), then \(G\) is \(2k\)-vertex deletable induced matching extendable. (3) If \(d(u) + d(v) \geq 2\lceil\frac{2v(G)+2k}{3} \rceil – 1\) for every two nonadjacent vertices \(u\) and \(v\), then \(G\) is \(2k\)-vertex deletable IM-extendable. Examples are given to show the tightness of all the conditions.