Secure Italian domination in graphs

An Italian dominating function (IDF) on a graph G is a function $$f:V(G)\rightarrow \{0,1,2\}$$ f : V ( G ) → { 0 , 1 , 2 } such that for every vertex v with $$f(v)=0$$ f ( v ) = 0 , the total weight of f assigned to the neighbours of v is at least two, i.e., $$\sum _{u\in N_G(v)}f(u)\ge 2$$ ∑ u ∈ N G ( v ) f ( u ) ≥ 2 . For any function $$f:V(G)\rightarrow \{0,1,2\}$$ f : V ( G ) → { 0 , 1 , 2 } and any pair of adjacent vertices with $$f(v) = 0$$ f ( v ) = 0 and u with $$f(u) > 0$$ f ( u ) > 0 , the function $$f_{u\rightarrow v}$$ f u → v is defined by $$f_{u\rightarrow v}(v)=1$$ f u → v ( v ) = 1 , $$f_{u\rightarrow v}(u)=f(u)-1$$ f u → v ( u ) = f ( u ) - 1 and $$f_{u\rightarrow v}(x)=f(x)$$ f u → v ( x ) = f ( x ) whenever $$x\in V(G){\setminus }\{u,v\}$$ x ∈ V ( G ) \ { u , v } . A secure Italian dominating function on a graph G is defined as an IDF f which satisfies that for every vertex v with $$f(v)=0$$ f ( v ) = 0 , there exists a neighbour u with $$f(u)>0$$ f ( u ) > 0 such that $$f_{u\rightarrow v}$$ f u → v is an IDF. The weight of f is $$\omega (f)=\sum _{v\in V(G) }f(v)$$ ω ( f ) = ∑ v ∈ V ( G ) f ( v ) . The minimum weight among all secure Italian dominating functions on G is the secure Italian domination number of G. This paper is devoted to initiating the study of the secure Italian domination number of a graph. In particular, we prove that the problem of finding this parameter is NP-hard and we obtain general bounds on it. Moreover, for certain classes of graphs, we obtain closed formulas for this novel parameter.