Further Results on the [k]-Roman Domination in Graphs
J.C. Valenzuela, Maria Antonia Mateos-Camacho, Martín Cera López, M. P. Álvarez-Ruiz · Bulletin of the Iranian Mathematical Society. · 2024
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\le k \le 4$$ 2 ≤ k ≤ 4 . Namely, f is a [k]-RDF if $$f(N[v])\ge 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.