Partial signed domination in graphs (Q2715936)

Let \(c,d\) be relatively prime positive integers, \(c \leq d\). A \(\tfrac {c}{d}\)-dominating function in a graph \(G\) with vertex set \(V\) is a function \(f:V\rightarrow \{-1,1\}\) such that for at least \(c|V|/d\) vertices \(v\) of \(G\) the sum \(f[v]\) of values of \(f\) in \(v\) and in all vertices adjacent to \(v\) is at least 1. The sum of all values of \(f\) is denoted by \(f(V)\). The minimum of \(f(V)\) taken over all \(\tfrac {c}{d}\)-dominating functions \(f\) in \(G\) is the \(\gamma \tfrac {c}{d}\)-domination number \(\gamma \tfrac {c}{d}(G)\) of \(G\). A sharp lower bound for \(\gamma \tfrac {c}{d}(G)\) for regular graphs \(G\) in terms of the number of vertices and of the regularity degree is found. Exact values of \(\gamma \tfrac {c}{d}(G)\) are determined for all circuits. The problem of determining the \(\tfrac {c}{d}\)-domination number of a given graph is shown to be NP-complete.