Some bounds on the maximum induced matching numbers of certain grids

Abstract

An induced matching $M$ in a graph $G$ is a matching in $G$ that is also the edge set of an induced subgraph of $G$. That is, any edge not in $M$ must have no more than one incident vertex saturated by $M$. The maximum size $|M|$ of an induced matching $M$ of $G$ is maximum induced matching number of $G$, which is denoted by $\text{Max}(G)$. In this article, we obtain upper bounds for $\text{Max}(G)$, for $G=G_{n,m}$, grids with $n,m\ge 9$, $m\equiv 1\mathrm{mod}4$ and $nm$ odd.