Induced Matchings in Graphs of Bounded Maximum Degree

Abstract

For a graph $G$, let ${\nu }_s(G)$ be the induced matching number of $G$. We prove that ${\nu }_s(G)\ge \frac{n(G)}{(\lceil \frac{\Delta }{2}\rceil +1)(\lfloor \frac{\Delta }{2}\rfloor +1)}$ for every graph of sufficiently large maximum degree $\Delta$ and without isolated vertices. This bound is sharp. Moreover, there is polynomial-time algorithm which computes induced matchings of size as stated above.

7 pages

Cited by in corpus (1)

• Induced Matchings in Graphs of Maximum Degree 4