Geodesic
Relating 2-Rainbow Domination To Roman Domination
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 953-961

Voir la notice de l'article provenant de la source Library of Science

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) ≤γ_R(G) ≤ 3/2 γ_r2 (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) − γ_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) = 3/2 γ_r2 (G).
Keywords: 2-rainbow domination, Roman domination 
@article{DMGT_2017_37_4_a6,
     author = {Alvarado, Jos\'e D. and Dantas, Simone and Rautenbach, Dieter},
     title = {Relating {2-Rainbow} {Domination} {To} {Roman} {Domination}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {953--961},
     publisher = {mathdoc},
     volume = {37},
     number = {4},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a6/}
}
TY  - JOUR
AU  - Alvarado, José D.
AU  - Dantas, Simone
AU  - Rautenbach, Dieter
TI  - Relating 2-Rainbow Domination To Roman Domination
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 953
EP  - 961
VL  - 37
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a6/
LA  - en
ID  - DMGT_2017_37_4_a6
ER  - 
%0 Journal Article
%A Alvarado, José D.
%A Dantas, Simone
%A Rautenbach, Dieter
%T Relating 2-Rainbow Domination To Roman Domination
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 953-961
%V 37
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a6/
%G en
%F DMGT_2017_37_4_a6
Alvarado, José D.; Dantas, Simone; Rautenbach, Dieter. Relating 2-Rainbow Domination To Roman Domination. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 953-961. http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a6/