- Tytuł:
- Relating 2-Rainbow Domination To Roman Domination
- Autorzy:
-
Alvarado, José D.
Dantas, Simone
Rautenbach, Dieter - Powiązania:
- https://bibliotekanauki.pl/articles/31341598.pdf
- Data publikacji:
- 2017-11-27
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
2-rainbow domination
Roman domination - Opis:
- For a graph $G$, let $ \gamma_R (G)$ and $ \gamma_{r2} (G) $ denote the Roman domination number of $G$ and the 2-rainbow domination number of $G$, respectively. It is known that $ \gamma_{r2} (G) \le \gamma_R(G) \le 3/2 \gamma_{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 $ \gamma_R (G) − \gamma_{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 $ \gamma_R (G) − \gamma_{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 $ \gamma_{r2} (H) = \gamma_R (H) $ for every induced subgraph $ H $ of $ G $, and collect several properties of the graphs $ G $ with $ \gamma_R (G) = 3/2 \gamma_{r2} (G) $.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 953-961
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł