RT journal article
T1 Complexity and Exact Values for [k]-Roman and Strong Roman Domination for Specific Graph Families
A1 Valenzuela Tripodoro, Juan Carlos
A1 Mateos Camacho, María Antonia
A1 Cera López, Martín
A1 Álvarez Ruiz, María del Pilar
A2 Estadística e Investigación Operativa
A2 Matemáticas
K1 Roman domination
K1 triple Roman domination
K1 strong Roman domination
K1 [k]-Roman domination
AB Motivated by the original idea of defending the Roman Empire, all these domination conceptscan be interpreted as vertex-labeling schemes that model the allocation of resources toprotect a graph against attacks. A Roman dominating function (RDF) is a labeling of the verticesof a graph with labels in {0, 1, 2} such that every vertex labeled 0 is adjacent to at leastone vertex labeled 2. The weight of an RDF is the sum of all vertex labels. Vertices labeled 2are intended to protect their neighbors labeled 0. The Roman domination number is theminimum weight of an RDF on the graph. In 2017, Álvarez et al. introduced strong Romandomination as a variant of Roman domination designed to protect the vertices of a graphagainst 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 thispaper, we investigate the computational complexity of the associated decision problems for[k]-Roman domination and strong Roman domination. Furthermore, we determine exactvalues of these parameters for several graph families under both variants.
PB MDPI
SN 2227-7390
YR 2026
FD 2026-05-01
LK http://hdl.handle.net/10498/39588
UL http://hdl.handle.net/10498/39588
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 05-nov-2026