Quasi-total Roman bondage number in graphs
AbstractA quasi-total Roman dominating function (QTRD-function) on [Formula: see text] is a function [Formula: see text] such that (i) every vertex x for which f(x) = 0 is adjacent to at least one vertex v for which f(v) = 2, and (ii) if x is an isolated vertex in the subgraph induced by the set of...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2022-09-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/09728600.2022.2098876 |
| _version_ | 1811315011838017536 |
|---|---|
| author | Huiqin Jiang Zehui Shao |
| author_facet | Huiqin Jiang Zehui Shao |
| author_sort | Huiqin Jiang |
| collection | DOAJ |
| description | AbstractA quasi-total Roman dominating function (QTRD-function) on [Formula: see text] is a function [Formula: see text] such that (i) every vertex x for which f(x) = 0 is adjacent to at least one vertex v for which f(v) = 2, and (ii) if x is an isolated vertex in the subgraph induced by the set of vertices with non-zero values, then f(x) = 1. The weight of a QTRD-function is the sum of its function values over the whole set of vertices, and the quasi-total Roman domination number is the minimum weight of a QTRD-function on G. The quasi-total Roman bondage number [Formula: see text] of a graph G is the minimum number of edges that have to be deleted to G in order to increase the quasi-total Roman domination number. In this paper, we start the study of quasi-total Roman bondage in graphs. We first show that the decision problem associated with the quasi-total Roman bondage problem is NP-hard even when restricted to bipartite graphs. Then basic properties of the quasi-total Roman bondage number are provided. Finally, some sharp bounds for [Formula: see text] are also presented. |
| first_indexed | 2024-04-13T11:22:40Z |
| format | Article |
| id | doaj.art-e2fd17de9b194b4899d364ebb9413507 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-04-13T11:22:40Z |
| publishDate | 2022-09-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-e2fd17de9b194b4899d364ebb94135072022-12-22T02:48:47ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742022-09-0119322122810.1080/09728600.2022.2098876Quasi-total Roman bondage number in graphsHuiqin Jiang0Zehui Shao1Institute of Computing Science and Technology, Guangzhou University, Guangzhou, ChinaInstitute of Computing Science and Technology, Guangzhou University, Guangzhou, ChinaAbstractA quasi-total Roman dominating function (QTRD-function) on [Formula: see text] is a function [Formula: see text] such that (i) every vertex x for which f(x) = 0 is adjacent to at least one vertex v for which f(v) = 2, and (ii) if x is an isolated vertex in the subgraph induced by the set of vertices with non-zero values, then f(x) = 1. The weight of a QTRD-function is the sum of its function values over the whole set of vertices, and the quasi-total Roman domination number is the minimum weight of a QTRD-function on G. The quasi-total Roman bondage number [Formula: see text] of a graph G is the minimum number of edges that have to be deleted to G in order to increase the quasi-total Roman domination number. In this paper, we start the study of quasi-total Roman bondage in graphs. We first show that the decision problem associated with the quasi-total Roman bondage problem is NP-hard even when restricted to bipartite graphs. Then basic properties of the quasi-total Roman bondage number are provided. Finally, some sharp bounds for [Formula: see text] are also presented.https://www.tandfonline.com/doi/10.1080/09728600.2022.2098876Quasi-total Roman domination numberquasi-total Roman bondage numbercomplexity05C0505C69 |
| spellingShingle | Huiqin Jiang Zehui Shao Quasi-total Roman bondage number in graphs AKCE International Journal of Graphs and Combinatorics Quasi-total Roman domination number quasi-total Roman bondage number complexity 05C05 05C69 |
| title | Quasi-total Roman bondage number in graphs |
| title_full | Quasi-total Roman bondage number in graphs |
| title_fullStr | Quasi-total Roman bondage number in graphs |
| title_full_unstemmed | Quasi-total Roman bondage number in graphs |
| title_short | Quasi-total Roman bondage number in graphs |
| title_sort | quasi total roman bondage number in graphs |
| topic | Quasi-total Roman domination number quasi-total Roman bondage number complexity 05C05 05C69 |
| url | https://www.tandfonline.com/doi/10.1080/09728600.2022.2098876 |
| work_keys_str_mv | AT huiqinjiang quasitotalromanbondagenumberingraphs AT zehuishao quasitotalromanbondagenumberingraphs |