Total 2-Rainbow Domination Numbers of Trees

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 \(\bigcup_{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, $\gamma_{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 $\gamma_{tr2}(G)$ is NP-complete for bipartite and chordal graphs.