Relating 2-Rainbow Domination To Roman Domination

• Autorzy: José D. Alvarado , Simone Dantas , Dieter Rautenbach
• Języki publikacji: EN

Abstrakty

EN

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).

Słowa kluczowe

EN

2-rainbow domination; Roman domination

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 4
• Strony: 953-961

Daty

wydano

2017-11-27

otrzymano

2015-12-03

poprawiono

2016-07-07

zaakceptowano

2016-08-08

online

2017-09-02

Twórcy

autor

José D. Alvarado

• ,

autor

Simone Dantas

• ,

autor

Dieter Rautenbach

• ,

Identyfikatory

DOI

10.7151/dmgt.1956