Quasi-total Roman reinforcement in graphs

Abstract

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 reinforcement number [Formula: see text] 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 [Formula: see text] are also presented.

Keywords

• Quasi-total Roman domination number
• quasi-total Roman reinforcement number
• complexity
• 05C05
• 05C69