New bounds on the \(k\)-domination number and the \(k\)-tuple domination number (Q2463933): Difference between revisions

The \(k\)-domination number \(\gamma_k(G)\) of a graph \(G\) is the cardinality of the smallest set \(D\) of vertices of \(G\) such that every vertex \(v\in V(G)\setminus D\) has at least \(k\) neighbors in \(D\); the \(k\)-tuple domination number \(\gamma_{\times k}\) is the smallest cardinility of a set \(D\) such that every vertex \(v\) of \(G\) has at least \(k\) neighbors in \(D\) (counting itself if \(v\in D\)). The authors prove the following two upper bounds on \(\gamma_k(G)\) and \(\gamma_{\times k}(G)\) for graph \(G\) with minimum degree \(\delta\) satisfying \(\frac{\delta+1}{\ln(\delta+1)}\geq 2k\): \[ \begin{aligned} \gamma_k(G) &\leq \frac{n}{\delta+1}\left(k\ln(\delta+1)+\sum_{i=0}^{k-1} \frac{1}{i!(\delta+1)^{k-1-i}}\right) \quad\text{and}\\ \gamma_{\times k}(G) &\leq \frac{n}{\delta+1}\left(k\ln(\delta+1)+\sum_{i=0}^{k-1} \frac{k-i}{i!(\delta+1)^{k-1-i}}\right).\end{aligned} \] The authors also provide a conjecture on a possible upper bound on \(\gamma_{\times k}(G)\) involving the degree sequence of a graph \(G\) which they verify for \(k=3\) as the case \(k=2\) is an earlier result of \textit{J. Harant} and \textit{M. A. Henning} [Discuss. Math., Graph Theory 25, 29--34 (2005; Zbl 1073.05049)].