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.
Categories: math.CO cs.DM cs.DS