Complexity of k-rainbow independent domination and some results on the lexicographic product of graphs.

Abstract A function f : V (G) → { 0 , 1 , ... , k } is called a k -rainbow independent dominating function of G if V i = { x ∈ V (G) : f (x) = i } is independent for 1 ≤ i ≤ k , and for every x ∈ V 0 it follows that N (x) ∩ V i ≠ ∅, for every i ∈ [ k ]. The k -rainbow independent domination number, γ ri k (G), of a graph G is the minimum of w (f) = ∑ i = 1 k | V i | over all such functions. In this paper we show that the problem of determining whether a graph has a k -rainbow independent dominating function of a given weight is NP-complete for bipartite graphs and that there exists a linear-time algorithm to compute γ ri k (G) of trees. In addition, sharp bounds for the k -rainbow independent domination number of the lexicographic product are presented, as well as the exact formula in the case k = 2. [ABSTRACT FROM AUTHOR]