Article ID Journal Published Year Pages File Type
435239 Theoretical Computer Science 2016 13 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,