p-Strong Roman Domination in Graphs
WSEAS Transactions on Mathematics
Doi 10.37394/23206.2024.23.104
Volumen 23
páginas 1005 - 1017
2024-01-01
Citas: 0
© 2024 World Scientific and Engineering Academy and Society. All rights reserved.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) ? {0, 1, 2, . . ., l ?+ppm } having the property that if f(v) = 0, then there is a vertex u ? N(v) such that f(u) ? 1 + l |B0?pN(u)|m , where B0 is the set of vertices with label 0. The p-strong Roman domination number ?StRp (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.
domination, graph, NP-complete problem, p-strong Roman domination, Roman domination, strong Roman domination
Datos de publicaciones obtenidos de
Scopus