- Tytuł:
- Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number
- Autorzy:
-
Poureidi, Abolfazl
Rad, Nader Jafari - Powiązania:
- https://bibliotekanauki.pl/articles/32312036.pdf
- Data publikacji:
- 2022-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
independent 2-rainbow dominating function
independent Roman {2}-dominating function
algorithm
3-SAT - Opis:
- A 2-rainbow dominating function (2RDF) of a graph $G$ is a function $g$ from the vertex set $V (G)$ to the family of all subsets of $ \{1, 2\}$ such that for each vertex $v$ with $g(v) =\emptyset $ we have \( \bigcup_{u∈N(v)} g(u) = \{ 1, 2 \} \). The minimum of $ g(V (G)) = \Sigma_{v \in V (G)} |g(v)| $ over all such functions is called the 2-rainbow domination number. A 2RDF $g$ of a graph $G$ is independent if no two vertices assigned non empty sets are adjacent. The independent 2-rainbow domination number is the minimum weight of an independent 2RDF of $G$. A Roman {2}-dominating function (R2DF) $ f : V \rightarrow \{ 0, 1, 2 \} $ of a graph $G = (V, E)$ has the property that for every vertex $ v \in V$ with $f(v) = 0$ either there is $ u \in N(v)$ with $f(u) = 2$ or there are $x, y \in N(v)$ with $f(x) = f(y) = 1$. The weight of $f$ is the sum $f(V) = \Sigma_{v \in V} f(v) $. An R2DF $f$ is called independent if no two vertices assigned non-zero values are adjacent. The independent Roman {2}-domination number is the minimum weight of an independent R2DF on $G$. We first show that the decision problem for computing the independent 2-rainbow (respectively, independent Roman {2}-domination) number is NP-complete even when restricted to planar graphs. Then, we give a linear algorithm that computes the independent 2-rainbow domination number as well as the independent Roman {2}-domination number of a given tree, answering problems posed in [M. Chellali and N. Jafari Rad, Independent 2-rainbow domination in graphs, J. Combin. Math. Combin. Comput. 94 (2015) 133–148] and [A. Rahmouni and M. Chellali, Independent Roman {2}-domination in graphs, Discrete Appl. Math. 236 (2018) 408–414]. Then, we give a linear algorithm that computes the independent 2-rainbow domination number of a given unicyclic graph.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 709-726
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł