Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number

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 {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.

Keywords

• independent 2-rainbow dominating function
• independent roman {2}-dominating function
• algorithm
• 3-sat
• 05c85
• 05c69