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 |
| _version_ | 1797244254448254976 |
|---|---|
| author | S. Kosari J. Amjadi M. Chellali F. Najafi S. M. Sheikholeslami |
| author_facet | S. Kosari J. Amjadi M. Chellali F. Najafi S. M. Sheikholeslami |
| author_sort | S. Kosari |
| collection | DOAJ |
| description | 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]. |
| first_indexed | 2024-03-12T13:29:13Z |
| format | Article |
| id | doaj.art-2c4fb262018d4d15a9c120562c3d864d |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-04-24T19:08:05Z |
| publishDate | 2024-01-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-2c4fb262018d4d15a9c120562c3d864d2024-03-26T14:03:25ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742024-01-0121110210910.1080/09728600.2023.2246529Independent k-rainbow bondage number of graphsS. Kosari0J. Amjadi1M. Chellali2F. Najafi3S. M. Sheikholeslami4Institute of Computing Science and Technology, Guangzhou University, Guangzhou, ChinaDepartment of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. IranLAMDA-RO Laboratory, Department of Mathematics, University of Blida, Blida, AlgeriaDepartment of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. IranDepartment of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. IranAbstractFor 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].https://www.tandfonline.com/doi/10.1080/09728600.2023.2246529Independent k-rainbow dominating functionindependent k-rainbow domination numberindependent k-rainbow bondage number05C69 |
| spellingShingle | S. Kosari J. Amjadi M. Chellali F. Najafi S. M. Sheikholeslami Independent k-rainbow bondage number of graphs AKCE International Journal of Graphs and Combinatorics Independent k-rainbow dominating function independent k-rainbow domination number independent k-rainbow bondage number 05C69 |
| title | Independent k-rainbow bondage number of graphs |
| title_full | Independent k-rainbow bondage number of graphs |
| title_fullStr | Independent k-rainbow bondage number of graphs |
| title_full_unstemmed | Independent k-rainbow bondage number of graphs |
| title_short | Independent k-rainbow bondage number of graphs |
| title_sort | independent k rainbow bondage number of graphs |
| topic | Independent k-rainbow dominating function independent k-rainbow domination number independent k-rainbow bondage number 05C69 |
| url | https://www.tandfonline.com/doi/10.1080/09728600.2023.2246529 |
| work_keys_str_mv | AT skosari independentkrainbowbondagenumberofgraphs AT jamjadi independentkrainbowbondagenumberofgraphs AT mchellali independentkrainbowbondagenumberofgraphs AT fnajafi independentkrainbowbondagenumberofgraphs AT smsheikholeslami independentkrainbowbondagenumberofgraphs |