Quasi-total Roman bondage number in graphs. Issue 3 (2nd September 2022)

• Record Type: Journal Article
• Authors: Jiang, Huiqin; Shao, Zehui
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 19:Issue 3(2022)
• Page Start: 221
• Page End: 228
• Publication Date: 2022-09-02
• Subjects: Quasi-total Roman domination number -- quasi-total Roman bondage number -- complexity; 05C05 -- 05C69
• DOI: 10.1080/09728600.2022.2098876
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: A quasi-total Roman dominating function (QTRD-function) on G = ( V, E ) is a function f : V → { 0, 1, 2 } 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 b qtR ( G ) 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 b qtR ( G ) are also presented.