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.