Relating $2$-rainbow domination to weak Roman domination

Abstract

Addressing a problem posed by Chellali, Haynes, and Hedetniemi (Discrete Appl. Math. 178 (2014) 27-32) we prove ${\gamma }_{r2}(G)\le 2{\gamma }_r(G)$ for every graph $G$, where ${\gamma }_{r2}(G)$ and ${\gamma }_r(G)$ denote the $2$-rainbow domination number and the weak Roman domination number of $G$, respectively. We characterize the extremal graphs for this inequality that are $\{K_4,K_4-e\}$-free, and show that the recognition of the $K_5$-free extremal graphs is NP-hard.