Maximal 2-rainbow domination number of a graph

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)=0̸ the condition ⋃u∈N(v)f(u)={1,2} is fulfilled, where N(v) is the open neighborhood of v. A maximal 2-rainbow dominating function on a graph G is a 2-rainbow dominating function f such that the set {w∈V(G)|f(w)=0̸} is not a dominating set of G. The weight of a maximal 2RDF f is the value ω(f)=∑v∈V|f(v)|. The maximal 2-rainbow domination number of a graph G, denoted by γmr(G), is the minimum weight of a maximal 2RDF of G. 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). In addition, we determine the maximal rainbow domination number of some graphs.

Abstract licence: CC BY-NC

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.