Algorithmic results for weak Roman domination problem in graphs

• Published in: Discrete Applied Mathematics 2024-12, Vol.359, p.278-289
• Main Authors: Paul, Kaustav, Sharma, Ankit, Pandey, Arti
• Format: Article
• Language: English
• Subjects: Bipartite graphs; Graph algorithms; NP-completeness; P4-sparse graphs; Split graphs; Weak Roman dominating function
• ISSN: 0166-218X
• DOI: 10.1016/j.dam.2024.08.007

Consider a graph G=(V,E) and a function f:V→{0,1,2}. A vertex u with f(u)=0 is defined as undefended by f if it lacks adjacency to any vertex with a positive f-value. The function f is said to be a weak Roman dominating function (WRD function) if, for every vertex u with f(u)=0, there exists a neighbor v of u with f(v)>0 and a new function f′:V→{0,1,2} defined in the following way: f′(u)=1, f′(v)=f(v)−1, and f′(w)=f(w), for all vertices w in V∖{u,v}; so that no vertices are undefended by f′. The total weight of f is equal to ∑v∈Vf(v), and is denoted as w(f). The Weak Roman domination number denoted by γr(G), represents min{w(f)|fis a WRD function ofG}. For a given graph G, the problem of finding a WRD function of weight γr(G) is defined as the Minimum Weak Roman domination problem. The problem is already known to be NP-hard for bipartite and chordal graphs. In this paper, we further study the algorithmic complexity of the problem. We prove the NP-hardness of the problem for star convex bipartite graphs and comb convex bipartite graphs, which are subclasses of bipartite graphs. In addition, we show that for the bounded degree star convex bipartite graphs, the problem is efficiently solvable. We also prove the NP-hardness of the problem for split graphs, a subclass of chordal graphs. On the positive side, we present a polynomial-time algorithm to solve the problem for P4-sparse graphs. Further, we have presented some approximation results.