Averaging $2$-Rainbow Domination and Roman Domination

Abstract

For a graph $G$, let ${\gamma }_{r2}(G)$ and ${\gamma }_R(G)$ denote the $2$-rainbow domination number and the Roman domination number, respectively. Fujita and Furuya (Difference between 2-rainbow domination and Roman domination in graphs, Discrete Applied Mathematics 161 (2013) 806-812) proved ${\gamma }_{r2}(G)+{\gamma }_R(G)\le \frac{6}{4}n(G)$ for a connected graph $G$ of order $n(G)$ at least $3$. Furthermore, they conjectured ${\gamma }_{r2}(G)+{\gamma }_R(G)\le \frac{4}{3}n(G)$ for a connected graph $G$ of minimum degree at least $2$ that is distinct from $C_5$. We characterize all extremal graphs for their inequality and prove their conjecture.