Upper bounds for the \(k\)-subdomination number of graphs (Q1598803)

For a graph \(G=(V,E)\) and a positive integer \(k\), a funktion \(f:V\to \{ -1,1\}\) is \(k\)-subdominating, if \(f(u)+\sum_{v\in N_G(u)}f(v)\geq 1\) for at least \(k\) vertices \(u\in V\). The minimum weight \(\sum_{u\in V}f(u)\) of a \(k\)-subdominating function of \(G\) is the \(k\)-subdomination number \(\gamma_{ks}(G)\) of \(G\). The authors prove that \(\gamma_{ks}(T)\leq 2k-n\) for a tree \(T\) of order \(n\) and \(\frac{n}{2}< k\leq n\) which was conjectured by \textit{E. J. Cockayne} and \textit{C. M. Mynhardt} [Ars Comb. 43, 235-245 (1996; Zbl 0881.05060)]. Furthermore, they prove that \(\gamma_{ks}(G)\leq 2 \left\lceil \frac{k}{n-k+1} \right\rceil (n-k+1)-n\) for a connected graph \(G\) of order \(n\) and \(\frac{n}{2}< k\leq n\). Whenever \(n-k+1\) divides \(k\) this implies another conjecture of Cockayne and Mynhardt which is false in general.