Independent k-rainbow bondage number of graphs

Abstract

AbstractFor an integer [Formula: see text] an independent k-rainbow dominating function (IkRDF for short) on a graph G is a function g that assigns to each vertex a set of colors chosen from the subsets of [Formula: see text] satisfying the following conditions: (i) if [Formula: see text], then [Formula: see text], and (ii) the set [Formula: see text] is an independent set. The weight of an IkRDF g is the value [Formula: see text]. The independent k-rainbow domination number [Formula: see text] is the minimum weight of an IkRDF on G. In this paper, we initiate a study of the independent k-rainbow bondage number [Formula: see text] of a graph G having at least one component of order at least three, defined as the smallest size of set of edges [Formula: see text] for which [Formula: see text]. We begin by showing that the decision problem associated with the independent k-rainbow bondage problem is NP-hard for general graphs for [Formula: see text]. Then various upper bounds on [Formula: see text] are established as well as exact values on it for some special graphs. In particular, for trees T of order at least three, it is shown that [Formula: see text].

Keywords

• Independent k-rainbow dominating function
• independent k-rainbow domination number
• independent k-rainbow bondage number
• 05C69