|
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
S
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) 6= ∅} 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.
|