Upper bounds for the k-subdomination number of graphs

For a positive integer k, a A-subdominating function of G = (lr,E) is a function f:V → {-1,1} such that the sum of the function values, taken over closed neighborhoods of vertices, is at least one for at least k vertices of G. The sum of the function values taken over all vertices is called the aggregate of / and the minimum aggregate among all Ar-subdominating functions of G is the t-subdomination number yt,(G). In this paper, we solve a conjecture proposed in (Ars. Combin 43 (1996) 235), which determines a sharp upper bound on yks(G) for trees if k > \V\/2 and give an upper bound on y is for connected graphs. © 2002 Elsevier Science B.V. All rights reserved.