ALGORITHMIC ASPECTS OF THE INDEPENDENT 2-RAINBOW DOMINATION NUMBER AND INDEPENDENT ROMAN f2g-DOMINATION NUMBER

Nader Jafari Rad | Abolfazl Poureidi

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=137637
Date :  2021/02/21
Publish in :    Discussiones Mathematicae Graph Theory
DOI :  https://doi.org/10.7151/dmgt.2299
Link :  https://www.dmgt.uz.zgora.pl/
Keywords :independent 2-rainbow dominating function, independent Ro- man f2g-dominating function, algorithm, 3-SAT.

Abstract :

---

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 f1; 2g such that for each vertex v with g(v) = ; we have S u2N(v) g(u) = f1; 2g. The minimum of g(V (G)) = P v2V (G) jg(v)j 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 f2g-dominating function (R2DF) f : V 􀀀 f0; 1; 2g of a graph G = (V;E) has the property that for every vertex v 2 V with f(v) = 0 either there is u 2 N(v) with f(u) = 2 or there are x; y 2 N(v) with f(x) = f(y) = 1. The weight of f is the sum f(V ) = P v2V f(v). An R2DF f is called independent if no two vertices assigned non-zero values are adjacent. The independent Roman f2g-domination number is the minimum weight of an independent R2DF on G.