Total 2-rainbow domination numbers of trees (Q2227097)

A function \(f:V(G) \rightarrow 2^{\{1,2\}}\) is a \(2\)-rainbow dominating function (2RDF) of a graph \(G\) if for every vertex \(v\) with \(f(v) = \emptyset\) we have \(\cup_{u\in N(v)} f(u) = \{1,2\}\). A 2RDF \(f\) is a total 2-rainbow dominating function (T2RDF) if the subgraph induced by the vertices \(v\) with \(f(v) \ne \emptyset\) has no isolated vertices. The total 2-rainbow domination number, \(\gamma_{tr2}(G)\) is the minimum weight of a T2RDF. In this paper sharp lower bounds and sharp upper bounds on \(\gamma_{tr2}(T)\) are given, where \(T\) is a tree. Lower bounds are expressed in terms of the order of \(T\), the number of its leaves and support vertices, and the total Roman domination number. Upper bounds are expressed in terms of the order of \(T\), the number of its support vertices, and the vertex cover number. It is also proved that the decision problem associated with \(\gamma_{tr2}\) is NP-complete for bipartite and chordal graphs.