Geodesic
Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 709-726

Voir la notice de l'article provenant de la source Library of Science

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) =∅ we have ⋃_u∈N(v) g(u) = { 1, 2 }. The minimum of g(V (G)) = Σ_v ∈ 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 →{ 0, 1, 2 } of a graph G = (V, E) has the property that for every vertex v ∈ V with f(v) = 0 either there is u ∈ N(v) with f(u) = 2 or there are x, y ∈ N(v) with f(x) = f(y) = 1. The weight of f is the sum f(V) = Σ_v ∈ 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.
Keywords: independent 2-rainbow dominating function, independent Roman {2}-dominating function, algorithm, 3-SAT 
@article{DMGT_2022_42_3_a1,
     author = {Poureidi, Abolfazl and Rad, Nader Jafari},
     title = {Algorithmic {Aspects} of the {Independent} {2-Rainbow} {Domination} {Number} and {Independent} {Roman} {{2}-Domination} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {709--726},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a1/}
}
TY  - JOUR
AU  - Poureidi, Abolfazl
AU  - Rad, Nader Jafari
TI  - Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 709
EP  - 726
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a1/
LA  - en
ID  - DMGT_2022_42_3_a1
ER  - 
%0 Journal Article
%A Poureidi, Abolfazl
%A Rad, Nader Jafari
%T Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 709-726
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a1/
%G en
%F DMGT_2022_42_3_a1
Poureidi, Abolfazl; Rad, Nader Jafari. Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 709-726. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a1/