Total 2-rainbow domination numbers of trees

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.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: Total 2-rainbow domination numbers of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227097)