A correction to a paper on Roman κ-domination in graphs

Abstract

Let G = (V,E) be a graph and k be a positive integer. A k- dominating set of G is a subset S ⊆ V such that each vertex in V＼S has at least k neighbors in S. A Roman k-dominating function on G is a function f : V ! {0, 1, 2} such that every vertex v with f(v) = 0 is adjacent to at least k vertices v1, v2, . . . , vk with f(vi) = 2 for i = 1, 2, . . . , k. In the paper titled “Roman k-domination in graphs” (J. Korean Math. Soc. 46 (2009), no. 6, 1309–1318) K. Kammerling and L. Volkmann showed that for any graph G with n vertices, kR(G) + kR(G)  min {2n, 4k + 1}, and the equality holds if and only if n  2k or k  2 and n = 2k + 1 or k = 1 and G or G has a vertex of degree n − 1 and its complement has a vertex of degree n − 2. In this paper we find a counterexample of Kammerling and Volkmann’s result and then give a correction to the result.