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, $Discuss.Math.GraphTheory$ $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.