Starred Italian domination in graphs

Abstract

An Italian dominating function on a graph $G$ is a function $f:V(G)\rightarrow \{0,1,2\}$ such that $\sum_{u\in N(v)}f(u)\geq 2$ for every vertex $v\in V_0$, where $V_0=\{v\in V(G) : f(v)=0\}$ and $N(v)$ represents the open neighbourhood of $v$. A starred Italian dominating function on $G$ is an Italian dominating function $f$ such that $V_0$ is not a dominating set of $G$. The starred Italian domination number of $G$, denoted $\gamma_{I}^*(G)$, is the minimum weight $\omega(f)=\sum_{v\in V(G)}f(v)$ among all starred Italian dominating functions $f$ on $G$.

In this article, we initiate the study of the starred Italian domination in graphs. For instance, we give some relationships that exist between this parameter and other domination invariants in graphs. Also, we present tight bounds and characterize the extreme cases. In addition, we obtain exact formulas for some particular families of graphs. Finally, we show that the problem of computing the starred Italian domination number of a graph is NP-hard.