Independent k-rainbow bondage number of graphs
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 [For...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2024-01-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/09728600.2023.2246529 |
| Summary: | 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]. |
|---|---|
| ISSN: | 0972-8600 2543-3474 |