Complexity of Roman {2}-domination and the double Roman domination in graphs. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Padamutham, Chakradhar; Palagiri, Venkata Subba Reddy
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 1081
• Page End: 1086
• Publication Date: 2020-09-01
• Subjects: Roman {2}-domination -- double Roman domination -- tree convex bipartite graphs -- NP-complete -- approximation algorithm; 05C69 -- 68Q25
• DOI: 10.1016/j.akcej.2020.01.005
• Languages: English
• ISSNs: 0972-8600

Abstract

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 .