Double Roman reinforcement number in graphs. Issue 3 (2nd September 2021)

• Record Type: Journal Article
• Authors: Amjadi, J.; Sadeghi, H.
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 18:Issue 3(2021)
• Page Start: 191
• Page End: 199
• Publication Date: 2021-09-02
• Subjects: Double Roman domination number -- double Roman reinforcement number -- complexity; 05C05 -- 05C69
• DOI: 10.1080/09728600.2021.1997557
• Languages: English
• ISSNs: 0972-8600

Abstract

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.