Relating 2-Rainbow Domination To Roman Domination

José D. Alvarado, Simone Dantas, and Dieter Rautenbach. "Relating 2-Rainbow Domination To Roman Domination." Discussiones Mathematicae Graph Theory 37.4 (2017): 953-961. <http://eudml.org/doc/288414>.

@article{JoséD2017,
abstract = {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).},
author = {José D. Alvarado, Simone Dantas, Dieter Rautenbach},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {2-rainbow domination; Roman domination},
language = {eng},
number = {4},
pages = {953-961},
title = {Relating 2-Rainbow Domination To Roman Domination},
url = {http://eudml.org/doc/288414},
volume = {37},
year = {2017},
}

TY - JOUR
AU - José D. Alvarado
AU - Simone Dantas
AU - Dieter Rautenbach
TI - Relating 2-Rainbow Domination To Roman Domination
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 4
SP - 953
EP - 961
AB - 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).
LA - eng
KW - 2-rainbow domination; Roman domination
UR - http://eudml.org/doc/288414
ER -