math.CO cs.DM cs.DS
Independent Double Roman Domination on Block Graphs. Given a graph G (V,E) , f V rightarrow 0,1,2 is the Italian dominating function of G if f satisfies sum u in N(v) f(u) geq 2 when f(v) 0 . Denote w(f) sum v in V f(v) as the weight of f . Let V i v f(v) i ,i 0,1,2 , we call f the independent Italian dominating function if V 1 cup V 2 is an independent set. The independent Italian domination number of G is the minimum weight of independent Italian dominating function f , denoted by i I (G) . We equivalently transform the independent domination problem of the connected block graph G to the induced independent domination problem of its block cutpoint graph T , then a linear time algorithm is given to find i I (G) of any connected block graph G based on dynamic programming.