On Proper 2-rainbow Domination in Graphs

Abstract

For a graph $G$, let $f : V(G) \rightarrow \mathcal{P}(\{1, 2,. . ., k\}$) be a function. If for each vertex $v\in V(G)$ such that $f(v) = \phi$ we have $\cup_{u \in N(v)} f(u) = \{1, 2, . . . , k\}$, then $f$ is called a $k$-rainbow dominating function (or simply $k$RDF) of $G$. The weight $w(f)$, of a $k$RDF $f$ is defined as $w(f) = \sum\limits_{v \in V(G)}^{}|f(v)|$. The minimum weight of a $k$RDF of $G$ is called the $k$-rainbow domination number of $G$, and is denoted by $\gamma_{rk}(G)$. In this paper we define and study a new domination called proper $k$-rainbow domination. A $k$-rainbow dominating function is called a proper $k$-rainbow dominating function if for every pair of adjacent vertices $u$ and $v$, $f(u)\not\subseteq f(v)$ and $f(v)\not\subseteq f(u)$. The weight, $w(f)$, of a proper $k$RDF $f$ is defined as $w(f) = \sum\limits_{v \in V(G)}^{}|f(v)|$. The minimum weight of a proper $k$RDF of $G$ is called the proper $k$-rainbow domination number of $G$, and is denoted by $\gamma_{prk}(G)$. The bounds for 2-rainbow domination and proper 2-rainbow domination for different classes of graphs namely cycles, complete multipartite graph, $P_{n}\times P_{m}$ and Harary graph are found.