Upper bounds on the kk-domination number and the kk-Roman domination number

Let GG be a graph and let kk be a positive integer. A subset DD of the vertex set of GG is a kk-dominating set   if every vertex not in DD has at least kk neighbors in DD. The kk-domination number  γk(G)γk(G) is the minimum cardinality among the kk-dominating sets of GG. A Roman  kk-dominating function   on GG is a function f:V(G)⟶{0,1,2}f:V(G)⟶{0,1,2} such that every vertex uu for which f(u)=0f(u)=0 is adjacent to at least kk vertices v1,v2,…,vkv1,v2,…,vk with f(vi)=2f(vi)=2 for i=1,2,…,ki=1,2,…,k. The weight   of a Roman kk-dominating function is the value f(V(G))=∑v∈V(G)f(v)f(V(G))=∑v∈V(G)f(v). The minimum weight of a Roman kk-dominating function on a graph GG is called the Roman  kk-domination number  γkR(G)γkR(G).In 2007, Rautenbach and Volkmann [D. Rautenbach, L. Volkmann, New bounds on the k-domination number and the k-tuple domination number, Appl. Math. Lett. 20 (2007) 98–102] gave an upper bound for the kk-domination number γk(G)γk(G). Using again the probabilistic method, we achieve better bounds for this parameter and prove new bounds for the kk-Roman domination number γkR(G)γkR(G). Moreover, we generalize known inequalities for the case k=1k=1 [V.I. Arnautov, Estimations of the external stability number of a graph by means of the minimal degree of vertices, Prikl. Mat. Programm. 11 (1974) 3–8 (in Russian); C. Payan, Sur le nombre d’absorption d’un graphe simple, Cahiers Centre Études Recherche Opér. 17 (1975) 307–317; E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22].