On the 2-rainbow domination stable graphs

Abstract

For a graph G, let $f:V(G)\rightarrow {\mathcal {P}}(\{1,2\}).$ If for each vertex $v\in V(G)$ such that $f(v)=\emptyset$ we have $\bigcup \nolimits _{u\in N(v)}f(u)=\{1,2\},$ then f is called a 2-rainbow dominating function (2RDF) of G. The weightw(f) of f is defined as $w(f)=\sum _{v\in V(G)}\left| f(v)\right|$. The minimum weight of a 2RDF of G is called the 2-rainbow domination number of G, which is denoted by $\gamma _{r2}(G)$. A graph G is 2-rainbow domination stable if the 2-rainbow domination number of G remains unchanged under removal of any vertex. In this paper, we prove that determining whether a graph is 2-rainbow domination stable is NP-hard and characterize 2-rainbow domination stable trees.