| Summary: | An outer-independent total dominating set (OITDS) of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V (G) \ D is independent. The outer-independent total domination number of a graph G, denoted by γ<sub>oit</sub>(G), is the minimum cardinality of an OITDS of G. An outer-independent total Roman dominating function (OITRDF) on a graph G is a function f : V(G) → {0, 1, 2} satisfying the conditions that every vertex u with f (u) = 0 is adjacent to at least one vertex v with f (v) = 2, every vertex x with f (x) ≥ 1 is adjacent to at least one vertex y with f (y) ≥ 1, and any two different vertices a, b with f (a) = f (b) = 0 are not adjacent. The minimum weight ω( f) = Σ<sub>v∈V(G)</sub> f (v) of any OITRDF f for G is the outer-independent total Roman domination number of G, denoted by γ<sub>oitR</sub>(G). A graph G is called an outer-independent total Roman graph (OIT-Roman graph) if γ<sub>oitR</sub>(G) = 2γ<sub>oit</sub>(G). In this paper, we propose dynamic programming algorithms to compute the outer-independent total domination number and the outer-independent total Roman domination number of a tree, respectively. Moreover, we characterize all OIT-Roman graphs and give a linear time algorithm for recognizing an OIT-Roman graph.
|
|---|