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

摘要

A function f:V(G)→{0,1,…,k} is called a k-rainbow independent dominating function of G if Vi={x∈V(G):f(x)=i} is independent for 1 ≤ i ≤ k, and for every x ∈ V0 it follows that N(x) ∩ Vi ≠ ∅, for every i ∈ [k]. The k-rainbow independent domination number, γrik(G), of a graph G is the minimum of w(f)=∑i=1k|Vi| 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 γrik(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.