On the k-domination, k-tuple domination and Roman k-domination numbers in graphs

摘要

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≥ 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 Etudes Recherche Oper. 17 (1975) 307-317] and Cockayne et al. [Discrete Math. 278 (2004), 11-22].