Computing Strong Roman Domination of Trees and Unicyclic Graphs in Linear Time

Nader Jafari Rad | A. Poureidi | N. Alawiah | H. Kamaruhali

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=169870
Date :  2022/05/07
Publish in :    Bulletin of the Malaysian Mathematical Sciences Society

Link :  https://link.springer.com/article/10.1007/s40840-022-01301-4
Keywords :Algorithm

Abstract :

---

For a graph G=(V,E) with maximum degree Δ, let f:V⟶0,1,…,⌈Δ2⌉+1 be a function and let Bi=v∈V:f(v)=i for each i∈0,1 and B2=v∈V:f(v)≥2=V−(B0∪B1). The function f is a strong Roman dominating function (StRDF) on G if every vertex v∈V with f(v)=0 is adjacent to a vertex u with f(u)≥⌈12NG(u)∩B0⌉+1. The weight of f is the sum f(V)=∑v∈Vf(v). The minimum weight of a StRDF on G is the strong Roman domination number of G. In this paper, we give a linear algorithm that computes the strong Roman domination number of trees, answering a problem which was posed in 2017. Then, we give a linear algorithm to compute the strong Roman domination number of unicyclic graphs.