Weighted restrained domination in subclasses of planar graphs

An undirected simple and connected graph is denoted by 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) denotes the subgraph of G induced by S. A subset Q of V is a restrained dominating set of G if U-u is an element of Q N[u] = V and no isolated vertices appear in (V - Q), where N(x)= {u vertical bar (u, x) is an element of E} and N[x] = N(x) U {x}, for all x is an element of V. This paper studies the Weighted Restrained Domination problem (the WRD problem) on graphs G (V, E, w), where w is a function giving a positive weight w(v) to each vertex v. The problem is to find a restrained dominating set D of the given graph G(V, E, w) and the objective is to minimize w(D) = Sigma(v is an element of D) w(v). When w(v) = 1, for all v is an element of 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. (C) 2016 Elsevier B.V. All rights reserved.