|
Abstract
|
A 2-rainbow dominating function (2RDF) on a graph 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 any vertex v ∈ V (G)
with f(v) = ∅ the condition Su∈N(v) f(u) = {1, 2} is fulfilled. A 2RDF f is independent
2-rainbow dominating function (I2RDF) if no two vertices assigned nonempty sets are
adjacent. The weight of a 2RDF f is the value ω(f) = Pv∈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. M. Chellali and
N. Jafari Rad [Independent 2-rainbow domination in graphs, to appear in J. Combin.
Math. Combin. Comput.] have studied the independent 2-rainbow domination numbers
in graphs and posed the following problem: Find a sharp bound for ir2(T) in terms
of the order of a tree T. In this paper we prove that for every tree T of order n ≥ 3,
ir2(T) ≤ 3n
4
|