An Upper Bound for the $k$-Tuple Domination Number

Abstract

We show that the double domination number of an $n$-vertex, isolate-free graph with minimum degree $\delta$ is bounded above by

$$\frac{n(\ln (\delta +1)+\ln \delta +1)}{\delta }.$$

This result improves a previous bound obtained by J. Harant and M. A. Henning [On double domination in graphs, \emph{Discuss. Math. Graph Theory} \textbf{25} (2005), 29-34]. Further, we show that for fixed $k$ and large $\delta$, the $k$-tuple domination number is at most

$$\frac{n(\ln \delta +(k–1+o(1))\ln \ln \delta )}{\delta },$$

a bound that is essentially best possible.