Skip to content

A note on the complexity of 2-rainbow domination

Oct 2026 · Asian-European Journal of Mathematics · 0 citations

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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.