2-Rainbow domination number of circulant graphs C(n; {1,4})

Abstract

Let $k$ be a positive integer. A $k$-rainbow domination function (kRDF) of a graph $G$ is a function $f$ from $V(G)$ to the set of all subsets of $\{1,2,\dots ,k\}$ such that every vertex $v\in V(G)$ with $f(v)=\varnothing$ satisfies ${\bigcup }_{u\in N(v)}f(u)=\{1,2,\dots ,k\}$. The weight of a $k$RDF is defined as $w(f)={\sum }_{v\in V(G)}|f(v)|$. The $k$-rainbow domination number of $G$, denoted by ${\gamma }_{rk}(G)$, is the minimum weight of all kRDFs of $G$. In this paper, we determine the exact value of the 2-rainbow domination number of circulant graphs $C(n;\{1,4\})$, which is ${\gamma }_{r2}(C(n;\{1,4\}))=\lceil n/3\rceil +\alpha$, where $\alpha =0$ for $n\equiv 0(\mathrm{mod}6)$, $\alpha =1$ for $n\equiv 1,2,3,5(\mathrm{mod}6)$, and $\alpha =2$ for $n\equiv 4(\mathrm{mod}6)$.