RT journal article
T1 p-Strong Roman Domination in Graphs
A1 Valenzuela Tripodoro, Juan Carlos
A1 Mateos Camacho, María Antonia
A1 Álvarez Ruiz, María del Pilar
A1 Cera López, Martín
A1 Moreno Casablanca, Rocio
A2 Estadística e Investigación Operativa
A2 Matemáticas
K1 graph
K1 NP-complete problem
K1 domination
K1 Roman domination
K1 strong Roman domination
K1 p-strong Roman domination
AB Domination in graphs is a widely studied field, where many different definitions have been introducedin the last years to respond to different network requirements. This paper presents a new dominatingparameter based on the well-known strong Roman domination model. Given a positive integer $p$, we calla $p$-strong Roman domination function ($p$-StRDF) in a graph $G$ to a function$f:V(G)\rightarrow  \{0,1,2, \ldots , \left\lceil \frac{\Delta+p}{p} \right\rceil \}$ having theproperty that if $f(v)=0$, then there is a vertex $u\in N(v)$ such that $f(u) \ge 1+ \left\lceil\frac{|B_0\cap N(u)|}{p} \right\rceil $, where $B_0$ is the set of vertices with label $0$. The$p$-strong Roman domination number $\gamma_{StR}^p(G)$ is the minimum weight (sum of labels) of a$p$-StRDF on $G$. We study the NP-completeness of the \emph{$p$-StRD}-problem, we alsoprovide general and tight upper and lower bounds depending on several classical invariants of the graphand, finally, we determine the exact values for some families of graphs.
YR 2024
FD 2024-12-17
LK http://hdl.handle.net/10498/35960
UL http://hdl.handle.net/10498/35960
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 10-may-2026