Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Relating 2-Rainbow Domination To Roman Domination

100%

Alvarado J. D., Dantas S., Rautenbach D.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 4

953-961

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

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Alvarado J. D.

1 Dantas S.

1 Rautenbach D.

1 2017

Wyniki wyszukiwania

Relating 2-Rainbow Domination To Roman Domination