For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(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 R(G) − yr2(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 K4-free graphs G with yR(G) − yr2(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 yr2(H) = yR(H) for every induced subgraph H of G, and collect several properties of the graphs G with R(G) = 3/2yr2(G).
@article{bwmeta1.element.doi-10_7151_dmgt_1956,
author = {Jos\'e D. Alvarado and Simone Dantas and Dieter Rautenbach},
title = {Relating 2-Rainbow Domination To Roman Domination},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {953-961},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1956}
}
José D. Alvarado; Simone Dantas; Dieter Rautenbach. Relating 2-Rainbow Domination To Roman Domination. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 953-961. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1956/