Secure Italian domination in graphs

Identificador:  imarina:9048287

Handle: https://hdl.handle.net/20.500.11797/imarina9048287

Autors:  Dettlaff, M; Lemanska, M; Rodriguez-Velazquez, J A

Resum:
An Italian dominating function (IDF) on a graph G is a function f : V(G) -> {0, 1, 2} such that for every vertex v with f (v) = 0, the total weight of f assigned to the neighbours of v is at least two, i.e., Sigma(u is an element of G(v)) f (u) >= 2. For any function f : V(G) -> {0, 1, 2} and any pair of adjacent vertices with f (v) = 0 and u with f (u) > 0, the function f(u -> v) is defined by f(u -> v)(v) = 1, f(u -> v)(u) = f (u) - 1 and f(u -> v)(x) = f ( x) whenever x is an element of 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, there exists a neighbour u with f (u) > 0 such that f(u -> v) is an IDF. The weight of f is.( f) = Sigma(v is an element of 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.