- Tytuł:
- Some Progress on the Double Roman Domination in Graphs
- Autorzy:
-
Rad, Nader Jafari
Rahbani, Hadi - Tematy:
-
Roman domination
double Roman domination - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/31343730.pdf Link otwiera się w nowym oknie
- Opis:
- For a graph $ G = (V,E) $, a double Roman dominating function (or just DRDF) is a function $ f : V \rightarrow {0, 1, 2, 3} $ having the property that if $ f(v) = 0 $ for a vertex $ v $, then $ v $ has at least two neighbors assigned 2 under $ f $ or one neighbor assigned 3 under $ f $, and if $ f(v) = 1 $, then vertex $ v $ must have at least one neighbor $ w $ with $ f(w) \ge 2 $. The weight of a DRDF $f$ is the sum $f(V) = \Sigma_{ v \in V } f(v) $, and the minimum weight of a DRDF on $G$ is the double Roman domination number of $G$, denoted by $ \gamma_{dR} (G) $. In this paper, we derive sharp upper and lower bounds on $ \gamma_{dR} (G) + \gamma_{dR} ( \overline{G} ) $ and also $ \gamma_{dR} (G ) \gamma_{dR} ( \overline{G} ) $, where $ \overline{G} $ is the complement of graph $G$. We also show that the decision problem for the double Roman domination number is NP- complete even when restricted to bipartite graphs and chordal graphs.
- Dostawca treści:
- Biblioteka Nauki
Artykuł