A Lower Bound for $2$-Rainbow Domination Number of Generalized Petersen Graphs P$(n,3)$

Abstract

Assume we have a set of $k$ colors and we assign an arbitrary subset of these colors to each vertex of a graph $G$. If we require that each vertex to which an empty set is assigned has in its neighborhood all $k$ colors, then this assignment is called the $k$-rainbow dominating function of a graph $G$. The minimum sum of numbers of assigned colors over all vertices of $G$, denoted as ${\gamma }_{rk}(G)$, is called the $k$-rainbow domination number of $G$. In this paper, we prove that ${\gamma }_{r2}(P(n,3))\ge \lceil \frac{7n}{8}\rceil .$