Back to Search Start Over

Algorithmic results for weak Roman domination problem in graphs.

Authors :
Paul, Kaustav
Sharma, Ankit
Pandey, Arti
Source :
Discrete Applied Mathematics. Dec2024, Vol. 359, p278-289. 12p.
Publication Year :
2024

Abstract

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 ∈ V f (v) , and is denoted as w (f). The Weak Roman domination number denoted by γ r (G) , represents m i n { w (f) | f is a WRD function of G }. 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 P 4 -sparse graphs. Further, we have presented some approximation results. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
0166218X
Volume :
359
Database :
Academic Search Index
Journal :
Discrete Applied Mathematics
Publication Type :
Academic Journal
Accession number :
180492627
Full Text :
https://doi.org/10.1016/j.dam.2024.08.007