On the $k$-domination, $k$-tuple Domination and Roman $k$-domination Numbers in Graphs

Abstract

Rautenbach and Volkmann [Appl. Math. Lett. 20 (2007), 98–102] gave an upper bound for the $k$-domination number and $k$-tuple domination number of a graph. Hansberg and Volkmann, [Discrete Appl. Math. 157 (2009), 1634–1639] gave upper bounds for the $k$-domination number and Roman $k$-domination number of a graph. In this note, using the probabilistic method and the known Caro-Wei Theorem on the size of the independence number of a graph, we improve the above bounds on the $k$-domination number, the $k$-tuple domination number and the Roman $k$-domination number in a graph for any integer $k\ge 1$. The special case $k=1$ of our bounds improve the known bounds of Arnautov and Payan [V.I. Arnautov, Prikl. Mat. Programm. 11 (1974), 3–8 (in Russian); C. Payan, Cahiers Centre Études Recherche Opér. 17 (1975) 307–317] and Cockayne et al. [Discrete Math. 278 (2004), 11–22].