Complexity of Roman {2}-domination and the double Roman domination in graphs. Issue 3 (1st September 2020) - Padamutham, Chakradhar; Palagiri, Venkata Subba Reddy
Abstract: For a simple, undirected graph G = ( V, E ), a Roman {2}-dominating function (R2DF) f : V → { 0, 1, 2 } has the property that for every vertex v ∈ V with f ( v ) = 0, either there exists a vertex u ∈ N ( v ), with f ( u ) = 2, or at least two vertices x, y ∈ N ( v ) with f ( x ) = f ( y ) = 1 . The weight of an R2DF is the sum f ( V ) = ∑ v ∈ V f ( v ) . The minimum weight of an R2DF is called the Roman {2}-domination number and is denoted by γ { R 2 } ( G ) . A double Roman dominating function (DRDF) on G is a function f : V → { 0, 1, 2, 3 } such that for every vertex v ∈ V if f ( v ) = 0, then v has at least two neighbors x, y ∈ N ( v ) with f ( x ) = f ( y ) = 2 or one neighbor w with f ( w ) = 3, and if f ( v ) = 1, then v must have at least one neighbor w with f ( w ) ≥ 2 . The weight of a DRDF is the value f ( V ) = ∑ v ∈ V f ( v ) . The minimum weight of a DRDF is called the double Roman domination number and is denoted by γ d R ( G ) . Given an graph G and a positive integer k, the R2DP (DRDP) problem is to check whether G has an R2DF (DRDF) of weight at most k . In this article, we first show that the R2DP problem is NP-complete for star convex bipartite graphs, comb convex bipartite graphs and bisplit graphs. We also show that the DRDP problem is NP-complete for star convex bipartite graphs and comb convex bipartite graphs. Next, we show that γ { R 2 } ( G ),  and  γ d R ( G ) are obtained in linear time for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs. Finally, we propose a 2 ( 1 +   ln   ( Δ + 1 ) ) -approximation algorithm for the minimum Roman {2}-domination problem and 3 ( 1 +   ln   ( Δ + 1 ) ) -approximation algorithm for the minimum double Roman domination problem, where Δ is the maximum degree of G .