Total 2-Rainbow Domination Numbers of Trees

Abstract

A 2-rainbow dominating function (2RDF) of a graph G = (V (G), E(G)) is a function f from the vertex set V (G) to the set of all subsets of the set {1, 2} such that for every vertex v ∈ V (G) with f(v) = ∅ the condition ∪u∈N(v)f(u) = {1, 2} is fulfilled, where N(v) is the open neighborhood of v. A total 2-rainbow dominating function f of a graph with no isolated vertices is a 2RDF with the additional condition that the subgraph of G induced by {v ∈ V (G) | f(v) ≠∅} has no isolated vertex. The total 2-rainbow domination number, γtr2(G), is the minimum weight of a total 2-rainbow dominating function of G. In this paper, we establish some sharp upper and lower bounds on the total 2-rainbow domination number of a tree. Moreover, we show that the decision problem associated with γtr2 (G) is NP-complete for bipartite and chordal graphs.

Keywords

• 2-rainbow dominating function
• 2-rainbow domination number
• total 2-rainbow dominating function
• total 2-rainbow domination number
• 05c69