Double Roman reinforcement number in graphs. Issue 3 (2nd September 2021) - Amjadi, J.; Sadeghi, H.
Abstract: For a graph G = ( V, E ), a double Roman dominating function is a function f : V ( G ) → 0, 1, 2, 3 having the property that if f ( v ) = 0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f ( w ) = 3, and if f ( v ) = 1, then vertex v must have at least one neighbor w with f ( w ) ≥ 2 . The weight of a double Roman dominating function f is the value ω ( f ) = Σ v ∈ V ( G ) f ( v ) . The double Roman domination number of a graph G, denoted by γ d R ( G ), equals the minimum weight of a double Roman dominating function on G . The double Roman reinforcement number r d R ( G ) of a graph G is the minimum number of edges that have to be added to G in order to decrease the double Roman domination number. In this paper, we first show that the decision problem associated to the double Roman reinforcement problem is NP-hard even when restricted to bipartite graphs and then we investigate the properties of double Roman reinforcement number in graphs, and we present some sharp bounds for r d R ( G ) . Next we characterize trees with double Roman reinforcement number greater than one.