|
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 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) = ∅} 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.
|