Degree conditions of nearly induced matching extendable graphs

Abstract

A graph $G$ is induced matching extendable (shortly, IM-extendable) if every induced matching of $G$ is included in a perfect matching of $G$. The IM-extendable graph was first introduced by Yuan. A graph $G$ is nearly IM-extendable if $G \vee K_1$ is IM-extendable. We show in this paper that: (1) Let $G$ be a graph with $2n-1$ vertices, where $n \geq 2$. If for each pair of nonadjacent vertices $u$ and $v$ in $G$, $d(u)+d(v) \geq 2 \lceil {{4n}/{3}}\rceil-3$, then $G$ is nearly IM-extendable. (2) Let $G$ be a claw-free graph with $2n-1$ vertices, where $n \geq 2$. If for each pair of nonadjacent vertices $u$ and $v$ in $G$, $d(u)+d(v) \geq 2n-1$, then $G$ is nearly IM-extendable. Minimum degree conditions of nearly IM-extendable graphs and nearly IM-extendable claw-free graphs are also obtained in this paper. It is also shown that all these results are best possible.