
arXiv: 1512.01067
For a graph $G$, let $��_R(G)$ and $��_{r2}(G)$ denote the Roman domination number of $G$ and the $2$-rainbow domination number of $G$, respectively. It is known that $��_{r2}(G)\leq ��_R(G)\leq \frac{3}{2}��_{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 $��_R(G)-��_{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 $��_R(G)-��_{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 $��_{r2}(H)=��_R(H)$ for every induced subgraph $H$ of $G$, and collect several properties of the graphs $G$ with $��_R(G)=\frac{3}{2}��_{r2}(G)$.
roman domination, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), 2-rainbow domination, Roman domination, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics
roman domination, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), 2-rainbow domination, Roman domination, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
