Complexity and Exact Values for [k]-Roman and Strong Roman Domination for Specific Graph Families

Abstract

Motivated by the original idea of defending the Roman Empire, all these domination concepts can be interpreted as vertex-labeling schemes that model the allocation of resources to protect a graph against attacks. A Roman dominating function (RDF) is a labeling of the vertices of a graph with labels in {0, 1, 2} such that every vertex labeled 0 is adjacent to at least one vertex labeled 2. The weight of an RDF is the sum of all vertex labels. Vertices labeled 2 are intended to protect their neighbors labeled 0. The Roman domination number is the minimum weight of an RDF on the graph. In 2017, Álvarez et al. introduced strong Roman domination as a variant of Roman domination designed to protect the vertices of a graph against multiple simultaneous attacks. In 2021, Ahangar et al. defined [k]-Roman domination, another model intended to defend a graph against individual attacks on vertices. In this paper, we investigate the computational complexity of the associated decision problems for [k]-Roman domination and strong Roman domination. Furthermore, we determine exact values of these parameters for several graph families under both variants.