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/

[1] J.D. Alvarado, S. Dantas and D. Rautenbach, Averaging 2-rainbow domination and Roman domination, Discrete Appl. Math. 205 (2016) 202-207. doi: 10.1016/j.dam.2016.01.021

[2] J.D. Alvarado, S. Dantas and D. Rautenbach, Relating 2-rainbow domination to weak Roman domination, arXiv:1507.04899.

[3] B. Breˇsar, M.A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213-225.

[4] M. Chellali, T.W. Haynes and S.T. Hedetniemi, Bounds on weak roman and 2- rainbow domination numbers, Discrete Appl. Math. 178 (2014) 27-32. doi: 10.1016/j.dam.2014.06.016

[5] M. Chellali and N.J. Rad, On 2-rainbow domination and Roman domination in graphs, Australas. J. Combin. 56 (2013) 85-93.

[6] S. Fujita and M. Furuya, Difference between 2-rainbow domination and Roman dom- ination in graphs, Discrete Appl. Math. 161 (2013) 806-812. doi: 10.1016/j.dam.2012.10.017

[7] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999) 136-139. doi: 10.1038/scientificamerican1299-136

[8] Y. Wu and N.J. Rad, Bounds on the 2-rainbow domination number of graphs, arXiv:1005.0988v1.

[9] Y. Wu and H. Xing, Note on 2-rainbow domination and Roman domination in graphs, Appl. Math. Lett. 23 (2010) 706-709. doi: 10.1016/j.aml.2010.02.012