Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees
Zepeng Li, Zehui Shao, Fangnian Lang, Xiaosong Zhang, Jia‐Bao Liu · IEEE Access · 2018
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 γoit(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) = Σv∈V(G)f (v) of any OITRDF f for G is the outer-independent total Roman domination number of G, denoted by γoitR(G). A graph G is called an outer-independent total Roman graph (OIT-Roman graph) if γoitR(G) = 2γoit(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.