|
Abstract
|
A 2-rainbow dominating function (2RDF) on a graph G = (V, E) is a
function f from the vertex set V to the set of all subsets of the set {1, 2} such that for any
vertex v ∈ V with f (v) = ∅the conditionu∈N(v) f (u) = {1, 2} is fulfilled.A2RDF
f is independent (I2RDF) if no two vertices assigned nonempty sets are adjacent. The
weight of a 2RDF f is the value ω( f ) = v∈V | f (v)|. The 2-rainbow domination
number γr2(G) (respectively, the independent 2-rainbow domination number ir2(G))
is the minimum weight of a 2RDF (respectively, I2RDF) on G. We say that γr2(G)
is strongly equal to ir2(G) and denote by γr2(G) ≡ ir2(G), if every 2RDF on G of
minimumweight is an I2RDF. In this paper,we provide a constructive characterization
of trees T with γr2(T ) ≡ ir2(T ).
|