Some Results on Dominating Induced Matchings

Abstract

Let $G$ be a graph, a dominating induced matching (DIM) of $G$ is an induced matching that dominates every edge of $G$. In this paper we show that if a graph $G$ has a DIM, then $\chi (G)⩽3$. Also, it is shown that if $G$ is a connected graph whose all edges can be partitioned into DIM, then $G$ is either a regular graph or a biregular graph and indeed we characterize all graphs whose edge set can be partitioned into DIM. Also, we prove that if $G$ is an $r$-regular graph of order $n$ whose edges can be partitioned into DIM, then $n$ is divisible by $\left(\genfrac{}{}{0ex}{}{2r-1}{r-1}\right)$ and $n=\left(\genfrac{}{}{0ex}{}{2r-1}{r-1}\right)$ if and only if $G$ is the Kneser graph with parameters $r-1$, $2r-1$.