Italian domination in generalized Petersen graphs

Abstract

In a graph $G=(V,E)$, each vertex $v\in V$ is labelled with $0$, $1$ or $2$ such that each vertex labelled with $0$ is adjacent to at least one vertex labelled $2$ or two vertices labelled $1$. Such kind of labelling is called an Italian dominating function (IDF) of $G$. The weight of an IDF $f$ is $w(f)={\sum }_{v\in V}f(v)$. The Italian domination number of $G$ is ${\gamma }_I(G)={\min }_{f}w(f)$. Gao et al. (2019) have determined the value of ${\gamma }_I(P(n,3))$. In this article, we focus on the study of the Italian domination number of generalized Petersen graphs $P(n,k)$, $k\ne 3$. We determine the values of ${\gamma }_I(P(n,1))$, ${\gamma }_I(P(n,2))$ and ${\gamma }_I(P(n,k))$ for $k\ge 4$, $k\equiv 2,3(\mathrm{mod}5)$ and $n\equiv 0(\mathrm{mod}5)$. For other $P(n,k)$, we present a bound of ${\gamma }_I(P(n,k))$. With the obtained results, we partially solve the open problem presented by Brešar et al. (2007) by giving $P(n,1)$ is an example for which ${\gamma }_I={\gamma }_{r2}$ and characterizing $P(n,2)$ for which ${\gamma }_I(P(n,2))={\gamma }_{r2}(P(n,2))$. Moreover, our results imply $P(n,1)$ $(n\equiv 0(\mathrm{mod}4))$ is Italian, $P(n,1)$ $(n\not\equiv 0(\mathrm{mod}4))$ and $P(n,2)$ are not Italian.