On the signed (total) k-domination number of a graph

Let k be a positive integer and G = (V, E) be a graph of minimum degree at least k - 1. A function f: V → {-1,1} is called a signed k-dominating function of G if Σu∈nG[v] f(u) ≥ k for all v ∈ V. The signed k-domination number of G is the minimum value of Σu∈v f(v) taken over all signed k-dominating functions of G. The signed total k-dominating function and signed total k-domination number of G can be similarly defined by changing the closed neighborhood Ng[v] to the open neighborhood Ng(v) in the definition. The upper signed k-domination number is the maximum value of Σu∈v f(v) taken over all minimal signed k-dominating functions of G. In this paper, we study these graph parameters from both algorithmic complexity and graph-theoretic perspectives. We prove that for every fixed k ≥ 1, the problems of computing these three parameters are all N P-hard. We also present sharp lower bounds on the signed k-domination number and signed total k-domination number for general graphs in terms of their minimum and maximum degrees, generalizing several known results about signed domination.