Abstract: Domination in graphs is a widely studied field, where many different definitions have been introduced in the last years to respond to different network requirements. This paper presents a new dominating parameter based on the well-known strong Roman domination model. Given a positive integer p, we call a p-strong Roman domination function (p-StRDF) in a graph G to a function $$f: V (G) \rightarrow \begin{Bmatrix} 0, 1, 2, ..., \begin{bmatrix} \frac{Δ+p}{p} \end{bmatrix}\end{Bmatrix}$$ having the property that if $$f(v) = 0$$, then there is a vertex $$ u \in 2 N(v) $$ such that $$ f(u)\geq 1+ \begin{bmatrix} \frac{\left.\begin{matrix} \end{matrix} \right|B_{0}\cap N(u)|}{p} \end{bmatrix} $$, where $$B_{0}$$ is the set of vertices with label 0. The p-strong Roman domination number $$ \gamma ^{p}_{StR} (G)$$ is the minimum weight (sum of labels) of a p-StRDF on G. We study the NP-completeness of the p-StRD-problem, we also provide general and tight upper and lower bounds depending on several classical invariants of the graph and, finally, we determine the exact values for some families of graphs.

Keywords: graph, NP-complete problem, domination, Roman domination, strong Roman domination, p-strong Roman domination.

Pages: 1005-1017