Perfect Roman {3}-Domination in Graphs: Complexity and Bound of Perfect Roman {3}-Domination Number of Trees

Ahlam Almulhim and Santi Spadaro

Journal of Mathematics, 2024, vol. 2024, 1-8

Abstract: A perfect Roman 3-dominating function on a graph G=V,E is a function f:V⟶0,1,2,3 having the property that if fv=0, then ∑u∈Nvfu=3, and if fv=1, then ∑u∈Nvfu=2 for any vertex v∈V. The weight of a perfect Roman 3-dominating function f is the sum ∑v∈Vfv. The perfect Roman 3-domination number of a graph G, denoted by γR3pG, is the minimum weight of a perfect Roman 3-dominating function on G. In this paper, we initiate the study of a perfect Roman 3-domination, and we show that the decision problem associated with a perfect Roman 3-domination is NP-complete for bipartite graphs. We also prove that if T is a tree of order n≥2, then γR3pT≤3n/2 and characterize trees achieving this bound, and we give an infinity set of trees T of order n for which γR3pT approaches this bound as n goes to infinity. Finally, we give the best upper bound of γR3pG for some classes of graphs including regular, planar, and split graphs in terms of the order of the graphs.

Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/jmath/2024/1900923.pdf (application/pdf)
http://downloads.hindawi.com/journals/jmath/2024/1900923.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jjmath:1900923

DOI: 10.1155/jom/1900923

Access Statistics for this article

More articles in Journal of Mathematics from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().