Quasi-total Roman reinforcement in graphs
N. Ebrahimi, Jafar Amjadi, Mustapha Chellali, Seyed Mahmoud Sheikholeslami · AKCE International Journal of Graphs and Combinatorics · 2022
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 reinforcement number rqtR(G) of a graph G is the minimum number of edges that have to be added to G in order to decrease the quasi-total Roman domination number. In this paper, we initiate the study of quasi-total Roman reinforcement in graphs. We first show that the decision problem associated with the quasi-total Roman reinforcement problem is NP-hard even when restricted to bipartite graphs. Then basic properties of the quasi-total Roman reinforcement number are provided. Finally, some sharp bounds for rqtR(G) are also presented.