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. Namely, f is a [k]-RDF if f (N [v]) ≥ k +|AN (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