The weighted perfect domination problem and its variants (Q1917310)

A perfect dominating set in a graph \(G\) is a subset \(D\) of the vertex set of \(G\) such that each vertex of \(G\) not in \(D\) is adjacent to exactly one vertex of \(D\). It is supposed that each vertex and each edge of \(G\) is labelled by a number called cost. For a subset \(D\) of the vertex set of \(G\) the total cost is the sum of costs of all vertices of \(D\) and of all edges having exactly one endvertex in \(D\). The weighted perfect domination problem is the problem to find a perfect dominating set \(D\) of \(G\) such that its total cost is minimum. Three variants of this problem are introduced, namely the problem to find a perfect dominating set which is moreover independent (induces a subgraph without edges), connected (induces a connected subgraph) or total (induces a subgraph without isolated vertices). These problems are proved to be NP-complete for bipartite graphs and chordal graphs, except the total perfect domination problem in chordal graphs. For these problems in block graphs linear-time algorithms are presented.