کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646490 | 1632248 | 2016 | 8 صفحه PDF | دانلود رایگان |
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.
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 13, Issue 2, August 2016, Pages 157–164