# Relating 2-Rainbow Domination To Roman Domination

José D. Alvarado; Simone Dantas; Dieter Rautenbach

Discussiones Mathematicae Graph Theory (2017)

- Volume: 37, Issue: 4, page 953-961
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJosé 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.