|
Abstract
|
A 2-rainbow dominating function (2RDF) of 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, where N(v) is the open
neighborhood of v. The weight of a 2RDF f is the value ω(f) = Pv∈V |f(v)|. The 2-
rainbow domination number of a graph G, denoted by γr2(G), is the minimum weight of
a 2RDF of G. The 2-rainbow domination subdivision number sdγr2 (G) is the minimum
number of edges that must be subdivided (each edge in G can be subdivided at most
once) in order to increase the 2-rainbow domination number. It is conjectured that for
any connected graph G of order n ≥ 3, sdγr2 (G) ≤ γr2(G). In this paper, we first prove
this conjecture for some classes of graphs and then we prove that for any connected
graph G of order n ≥ 3, sdγr2 (G) ≤ 2γr2(G) − 2.
|