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.