Generalized domination and efficient domination in graphs (Q1126173)

The closed neighbourhood of a vertex \(v\) of a graph \(G\) is the set consisting of \(v\) and of all vertices adjacent to \(v\) in \(G\). A function \(f\) which maps the vertex set \(V(G)\) of \(G\) onto a subset \(Y\) of the set of real numbers is called \(Y\)-dominating in \(G\), if the sum of its values over the closed neighbourhood of each vertex \(v\) of \(G\) is at least 1. If it is exactly 1 for each vertex, then \(f\) is called a \(Y\)-domination function on \(G\). The weight \(w(f)\) of \(f\) is the sum of values of \(f\) over \(V(G)\). The minimum weight of a \(Y\)-domination function in \(G\) is the \(Y\)-domination number \(\gamma_Y(G)\) of \(G\). A necessary and sufficient condition for the existence of a \(Y\)-dominating function in a graph \(G\) and a sufficient condition for the existence of an efficient \(Y\)-domination function are presented. The problem to decide whether in a given graph there exists an efficient \(Y\)-domination function with \(Y=\{-1,1\}\) (the signed domination function) is shown to be NP-complete.