Weighted restrained domination in subclasses of planar graphs

An undirected simple and connected graph is denoted by G(V,E)G(V,E), where V and E are the vertex-set and the edge-set of G, respectively. For any subset S   of V,〈S〉V,〈S〉 denotes the subgraph of G induced by S. A subset Q of V is a restrained dominating set of G   if ⋃u∈QN[u]=V⋃u∈QN[u]=V and no isolated vertices appear in 〈V−Q〉〈V−Q〉, where N(x)={u|(u,x)∈E}N(x)={u|(u,x)∈E} and N[x]=N(x)∪{x}N[x]=N(x)∪{x}, for all x∈Vx∈V. This paper studies the Weighted Restrained Domination problem (the WRD problem) on graphs G(V,E,w)G(V,E,w), where w   is a function giving a positive weight w(v)w(v) to each vertex v. The problem is to find a restrained dominating set D   of the given graph G(V,E,w)G(V,E,w) and the objective is to minimize w(D)=∑v∈Dw(v)w(D)=∑v∈Dw(v). When w(v)=1w(v)=1, for all v∈Vv∈V, the WRD problem is abbreviated as the RD problem. The first result shows that the WRD problem on cactus graphs can be solved in linear time. The second result proves that the RD problem on planar bipartite graphs remains NP-hard.