| Summary: | <p>A function <em>f</em>:<em>V</em> → {0,1,2} is a total Roman dominating function (TRDF) on a graph <em>G</em>=(<em>V,E</em>) if for every vertex <em>v</em> ∈ <em>V</em> with <em>f</em>(<em>v</em>) = 0 there is a vertex <em>u</em> adjacent to <em>v</em> with <em>f</em>(<em>u</em>) = 2 and for every vertex <em>v </em>∈<em> V</em> with <em>f</em>(<em>v</em>) > 0 there exists a vertex <em>u</em> ∈ <em>N</em><sub><em>G</em>(<em>v</em>)</sub> with <em>f</em>(<em>u</em>) > 0. The weight of a total Roman dominating function <em>f</em> on <em>G</em> is equal to <em>f</em>(<em>V</em>)=Σ<sub>v ∈ V</sub><em>f</em>(<em>v</em>). The minimum weight of a total Roman dominating function on <em>G</em> is called the total Roman domination number of <em>G</em>. In this paper, we give an algorithm to compute the total Roman domination number of a given proper interval graph <em>G</em>=(<em>V,E</em>) in <em>O</em>(|<em>V</em>|) time.</p>
|
|---|