Algorithmic aspects of total k-subdomination in graphs

Let G = (V, E) be a graph and let k ∈ Z. A total k-subdominating function is a function f : V → {−1, 1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V ) over all total k-subdominating functions f of G where f(V ) denotes the sum of the function values assigned to the vertices under f . In this paper, we present a cubic time algorithm to compute the total k-subdomination number of a tree and also show that the associated decision problem is NP-complete for general graphs.