Perfect Italian domination in graphs: Complexity and algorithms

An Italian dominating function on a simple undirected graph G is a function f : V(G) -> {0, 1, 2} satisfying the condition that for each vertex v with f (v) = 0, Sigma(u epsilon NG(v)) f(u) >= 2. An Italian dominating function f on G is called a perfect Italian dominating function on G if for each vertex v with f (v) = 0, Sigma(u epsilon NG(v)) f (u) = 2. The weight of a function f on a graph G, denoted by w(f), is the sum Sigma(u epsilon V(G)) f (v). For a simple undirected graph G, Min-PIDF is the problem of finding the minimum weight of a perfect Italian dominating function on G. First, we discuss the complexity difference between Min-PIDF and the problem of finding the minimum weight of an Italian dominating function. We then establish the NP-completeness of the decision version of Min-PIDF in chordal graphs and investigate the hardness of approximation of Min-PIDF in general graphs. Finally, we present linear time algorithms for computing the minimum weight of a perfect Italian dominating function in block graphs and series-parallel graphs. (c) 2021 Elsevier B.V. All rights reserved.