\(k\)-subdomination in graphs (Q1613364)

A function assigning \(1\) or \(-1\) to each vertex of a graph \(G\), so that the function values sum to at least \(+1\) for the neighborhoods of at least \(k\) vertices is called a \(k\)-subdominating function. The \(k\)-subdomination number \(\gamma_{ks}(G)\) is the minimum, over all \(k\)-subdominating functions, of the total sum of function values. It is proven here for a tree \(T\) on \(n\) vertices and \(n/2 <k \leq n\) that \(\gamma_{ks}(T)\leq 2k-n\), setteling a conjecture of \textit{E. J. Cockayne} and \textit{C. M. Mynhardt} [Ars Comb. 43, 235-245 (1996; Zbl 0881.05060)]. Some lower bounds are also given. An independent proof of the main result was also obtained by \textit{L. Kang, C. Dang, M. Cai}, and \textit{E. Shan} [Discrete Math. 247, 229-234 (2002; Zbl 0990.05098)].