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

For a graph G = (V , E) with maximum degree Δ , let f : V ⟶ { 0 , 1 , ... , ⌈ Δ 2 ⌉ + 1 } be a function and let B i = { v ∈ V : f (v) = i } for each i ∈ { 0 , 1 } and B 2 = { v ∈ V : f (v) ≥ 2 } = V - (B 0 ∪ B 1) . 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) ≥ ⌈ 1 2 | N G (u) ∩ B 0 | ⌉ + 1 . The weight of f is the sum f (V) = ∑ v ∈ V f (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. [ABSTRACT FROM AUTHOR]