A note on the complexity of 2-rainbow domination
Abstract
A [Formula: see text]-rainbow dominating function of a graph [Formula: see text] is a function [Formula: see text] that assigns to each vertex a set of colors chosen from the set [Formula: see text] so that for each vertex [Formula: see text] with [Formula: see text] we have [Formula: see text] The minimum value of [Formula: see text] over all such functions is called the [Formula: see text]-rainbow domination number [Formula: see text]. In this paper we prove that the decision problem associated with the 2-rainbow domination is NP-complete even when restricted to star or double star convex bipartite graphs.