Further Results on the k-Roman Domination in Graphs

Abstract In 2016, Beeler et al. defined the double Roman domination as a variation of Roman domination. Sometime later, in 2021, Ahangar et al. introduced the concept of k -Roman domination in graphs and settled some results on the triple Roman domination case. In 2022, Amjadi et al. studied the quadruple version of this Roman-domination-type problem. Given any labeling of the vertices of a graph, AN (v) stands for the set of neighbors of a vertex v having a positive label. In this paper we continue the study of the k -Roman domination functions (k -RDF) in graphs which coincides with the previous versions when 2 k 4 2 ≤ k ≤ 4. Namely, f is a k -RDF if f (Nv) k+|AN (v) | f (N v) ≥ k + | A N (v) | for all v. We prove that the associate decision problem is NP-complete even when restricted to star convex and comb convex bipartite graphs and we also give sharp bounds and exact values for several classes of graphs.