Relating 2-Rainbow Domination To Roman Domination

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 3/2 \gamma_{r2} (G) $. Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 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) = 3/2 \gamma_{r2} (G) $.