Minus \(k\)-subdomination in graphs. II (Q1363694)

\(N(v)\), the open neighbourhood of a vertex \(v\) in an undirected graph \(G=(V,E)\), is the set of vertices adjacent to \(v\); for \(S\subseteq V\), \(N(S)=\bigcup_{v\in S}N(v)\), the ``closed'' neighbourhood \(N[S]\) is \(N(V)\cup S\). For a positive integer \(k \leq |V|\), a function \(f:V\rightarrow \{-1,0,1\}\) is a \(k\)-subdominating function if \(f(N[v])\geq1\) for at least \(k\) vertices \(v\in V\), where, for any \(S\subseteq V\), \(f(S)\) is defined to be \(\sum_{v\in S}f(v)\). The \(k\)-subdomination number of \(G\), \(\gamma_{ks}^{-101}(G)\) is the minimum of \(f(V)\) over all \(k\)-subdominating functions. Theorem 3. If \(T\) is a tree of order \(n\geq 2\), and \(k\) is an integer such that \(1\leq k\leq n-1\), then \(\gamma_{ks}^{-101}(T)\geq k-n+2\). Moreover, this bound is best possible. Theorem 5. If \(k\) and \(n\) are integers such that \(1\leq k\leq n-1\), then \(\gamma_{ks}^{-101}(C_n)= \left\lceil\frac{n-2}3\right\rceil\) if \(k=n-1\) and (\(k\equiv 0\) or \(k\equiv 1\pmod{3}\)), and \(\gamma_{ks}^{-101}(C_n)= 2\left\lfloor\frac{2k+4}3\right\rfloor-n\) otherwise. The paper applies results of a paper ``Minus \(k\)-subdomination in graphs'' by J. Broere, J. E. Dunbar, and the first named author, and shown as ``submitted''.