Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646490 | AKCE International Journal of Graphs and Combinatorics | 2016 | 8 Pages |
A 2-rainbow dominating function (2RDF) of a graph GG is a function ff from the vertex set V(G)V(G) to the set of all subsets of the set {1,2}{1,2} such that for any vertex v∈V(G)v∈V(G) with f(v)=0̸f(v)=0̸ the condition ⋃u∈N(v)f(u)={1,2}⋃u∈N(v)f(u)={1,2} is fulfilled, where N(v)N(v) is the open neighborhood of vv. A maximal 2-rainbow dominating function on a graph GG is a 2-rainbow dominating function ff such that the set {w∈V(G)|f(w)=0̸}{w∈V(G)|f(w)=0̸} is not a dominating set of GG. The weight of a maximal 2RDF ff is the value ω(f)=∑v∈V|f(v)|ω(f)=∑v∈V|f(v)|. The maximal 2-rainbow domination number of a graph GG, denoted by γmr(G)γmr(G), is the minimum weight of a maximal 2RDF of GG. In this paper we initiate the study of maximal 2-rainbow domination number in graphs. We first show that the decision problem is NP-complete even when restricted to bipartite or chordal graphs, and then, we present some sharp bounds for γmr(G)γmr(G). In addition, we determine the maximal rainbow domination number of some graphs.