Outer-independent k-rainbow domination

Abstract

An outer-independent k-rainbow dominating function of a graph G is a function f from $V(G) $ to the set of all subsets of $\{1,2,\ldots ,k\} $ such that both the following hold: (i) $\{1,\ldots ,k\}=\bigcup _{u\in N(v)} f(u) $ whenever v is a vertex with $f(v)=\emptyset $, and (ii) the set of all $v \in V(G) $ with $f(v)= \emptyset $ is independent. The outer-independent k-rainbow domination number of G is the invariant $\gamma _{oir}^k(G) $, which is the minimum sum (over all the vertices of G) of the cardinalities of the subsets assigned by an outer-independent k-rainbow dominating function. In this paper, we initiate the study of outer-independent k-rainbow domination. We first investigate the basic properties of the outer-independent k-rainbow domination and then we focus on the outer-independent 2-rainbow domination number and present sharp lower and upper bounds for it.

Keywords

• k-rainbow dominating function
• k-rainbow domination
• outer-independent domination