Partial Signed Domination in Graphs

Let \(G = (V, E)\) be a graph. For any real valued function \(f: V \to \mathbb{R}\) and \(S \subseteq V\), let \(f(S) = \sum_{u \in S} f(u)\). Let \(c, d\) be positive integers such that \(\gcd(c, d) = 1\) and \(0 < \frac{c}{d} \leq 1\). A \(\frac{c}{d}\)-dominating function \(f\) is a function \(f: V \to \{-1, 1\}\) such that \(f[v] \geq 1\) for at least \(\frac{c}{d}\) of the vertices \(v \in V\). The \(\frac{c}{d}\)-domination number of \(G\), denoted by \(\gamma_{\frac{c}{d}}(G)\), is defined as \(\min\{f(V) | f\) is a \(\frac{c}{d}\)-dominating function on \(G\}\). We determine a sharp lower bound on \(\gamma_{\frac{c}{d}}(G)\) for regular graphs \(G\), determine the value of \(\gamma_{\frac{c}{d}}(G)\) for an arbitrary cycle \(C_n\), and show that the decision problem PARTIAL SIGNED DOMINATING FUNCTION is \(NP\)-complete.