Relations between the Roman k-domination and Roman domination numbers in graphs

摘要

Let G = (V, E) be a graph and let k be a positive integer. A Roman k-dominating function (Rk-DF) on G is a function f: V(G) → {0,1,2} such that every vertex u for which f(u) = 0 is adjacent to at least k vertices v_1,v_2,...,u_k with f(u_i)= 2 for i = 1,2,..., k. The weight of an Rk-DF is the value f(V(G)) = Σ_(u∈V(G)) f(u) and the minimum weight of an Rk-DF on G is called the Roman k-domination number γkR(G) of G. In this paper, we present relations between γkR(G) and γR(G). Moreover, we give. characterizations of some classes of graphs attaining equality in these relations. Finally, we establish a relation between γkR(G) and γR(G) for {K 1,3, Ki,3+e}-free graphs and we characterize all such graphs G with γkR(G) = γR(G) + t, where t ∈ {2k -3,2k -2,[n/3|}.