Independent k -rainbow bondage number of graphs

• Published in: AKCE international journal of graphs and combinatorics 2024-01, Vol.21 (1), p.102-109
• Main Authors: Kosari, S., Amjadi, J., Chellali, M., Najafi, F., Sheikholeslami, S. M.
• Format: Article
• Language: English
• Subjects: 05C69; independent k-rainbow bondage number; Independent k-rainbow dominating function; independent k-rainbow domination number
• ISSN: 0972-8600; 2543-3474
• DOI: 10.1080/09728600.2023.2246529

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].