Relating $2$-Rainbow Domination to Roman domination

Abstract

For a graph $G$, let ${\gamma }_R(G)$ and ${\gamma }_{r2}(G)$ denote the Roman domination number of $G$ and the $2$-rainbow domination number of $G$, respectively. It is known that ${\gamma }_{r2}(G)\le {\gamma }_R(G)\le \frac{3}{2}{\gamma }_{r2}(G)$. Fujita and Furuya (Difference between 2-rainbow domination and Roman domination in graphs, Discrete Applied Mathematics 161 (2013) 806-812) present some kind of characterization of the graphs $G$ for which ${\gamma }_R(G)-{\gamma }_{r2}(G)=k$ for some integer $k$. Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs efficiently. We show that for every fixed non-negative integer $k$, the recognition of the connected $K_4$-free graphs $G$ with ${\gamma }_R(G)-{\gamma }_{r2}(G)=k$ is NP-hard, which implies that there is most likely no good characterization of these graphs. We characterize the graphs $G$ such that ${\gamma }_{r2}(H)={\gamma }_R(H)$ for every induced subgraph $H$ of $G$, and collect several properties of the graphs $G$ with ${\gamma }_R(G)=\frac{3}{2}{\gamma }_{r2}(G)$.