WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 23, 2024
p-Strong Roman Domination in Graphs
Authors: , , , ,
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.
Search Articles
Keywords: graph, NP-complete problem, domination, Roman domination, strong Roman domination, p-strong Roman domination.
Pages: 1005-1017
DOI: 10.37394/23206.2024.23.104