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)\ge \lceil \frac{v(G)}{3}\rceil +1$ and $max\{d(u),d(v)\}\ge \frac{2v(G)+1}{3}$ for every two nonadjacent vertices $u$ and $v$, then $G$ is induced matching extendable. (2) If $\kappa (G)\ge \lceil \frac{v(G)+4k}{3}\rceil$ and $max\{d(u),d(v)\}\ge \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)\ge 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.