Further results on the signed Italian domination

Abstract

A signed Italian dominating function on a graph $G=(V,E)$ is a function $f: V\rightarrow \{-1, 1, 2\}$ satisfying the condition that for every vertex u, $f[u]\ge 1$. The weight of the signed Italian dominating function, f, is the value $f(V)=\sum _{u\in V}f(u)$. The signed Italian dominating number of a graph G, denoted by $\gamma _{sI}(G)$, is the minimum weight of a signed Italian dominating function on a graph G. In this paper, we prove that for any tree T of order $n\ge 2$, $\gamma _{sI}(T)\ge \frac{-n+4}{2}$ and we characterize all trees attaining this bound. In addition, we obtain some results about the signed Italian domination number of some graph operations. Furthermore, we prove that the signed Italian domination problem is $\mathbf {NP}$-Complete for bipartite graphs.

1 Introduction

In this paper, G is a simple graph with the vertex set $V=V(G)$ and the edge set $E=E(G)$. The order |V| of G is denoted by n. For every vertex $v\in V,$ the $\textit{open neighborhood}$ N(v) is the set $\{u\in V(G)\ | \ uv\in E(G)\}$ and the $\textit{closed neighborhood}$ of v is the set $N[v]=N(v)\cup \{v\}$. For every vertex $v\in V$ the number of neighbors of v is denoted by $deg_{G}(v)$. We denote $deg_{G}(v)$ by $d_{G}(v)$ for notational convenience. The $\textit{ minimum}$ and $\textit{maximum}$ degree of a graph G are denoted by $\delta$ and $\Delta$, respectively.

A $\textit{signed dominating function}$ (SDF) on a graph $G=(V,E)$ is a function $f:V \rightarrow \{ -1, 1 \}$ such that $f[v]\ge 1$ for every vertex $v\in V$. The signed domination number, denoted by $\gamma _{s} (G)$, is the minimum weight of a SDF in G; that is, $\gamma _{s}(G)=\min \{ w(f) \ | \ f \mathrm{\ is \ a \ SDF \ in\ } G \}$.

An $\textit{Italian dominating function}$ (IDF) or a $\textit{Roman }${2}-dominating function on a graph $G=(V,E)$ is a function $f:V\rightarrow \{ 0, 1, 2 \}$ with the property that for every vertex $v \in V$ with $f(v)=0$, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to at least two vertices assigned 1 under f. The $\textit{Italian domination}$ $\textit{function number}$ $\gamma _{I}(G)$ equals to the minimum weight of an Italian dominating function on G. An Italian domination has been introduced in 2015 by Chellali et al. [1], and studied further in [4, 5].

In this paper, we continue the study of the signed Italian domination in graphs introduced in [6] as follows. A $\textit{signed Italian dominating function}$ (SIDF) on graph $G=(V,E)$ is a function $f:V \rightarrow \{-1, 1, 2\}$ which has the property that for every vertex $v\in V$ the sum of the values assigned to vertex v and its neighbors is at least 1. Thus a signed Italian dominating function combines the properties of both an Italian dominating function and a signed dominating function. The signed Italian domination number, denoted by $\gamma _{sI}(G)$, is the minimum weight of a SIDF in G; that is, $\gamma _{sI}(G)=\min \{ w(f) \ | \mathrm{\ f \ is \ a \ SIDF \ in\ } G \}$. A SIDF of weight $\gamma _{sI}(G)$ is called a $\gamma _{sI}(G)$-function. For a vertex $v\in V$, we denote f(N[v]) by f[v] for notational convenience. For a SIDF f on G, let $V_{i}= \{ v\in V(G) \ | \ f(v)=i \}$ for $i=-1,1,2$. In the context of a fixed SIDF, we suppress the argument and simply write $V_{-1}$, $V_{1}$ and $V_{2}$. Since this partition determines f, we can equivalently write $f=(V_{-1}, V_{1}, V_{2})$.

A $\textit{ tree}$ on n vertices is denoted by $T_{n}$. A leaf of T is a vertex with degree one and a support vertex is a vertex adjacent to a leaf. A tree T is a double star if it contains exactly two vertices that are not leaves. A double star with respectively p and q leaves attached at each support vertex is denoted by $DS_{p,q}$. The $\textit{distance}$ $d_{G}(u, v)$ between two vertices u and v in a connected graph G is the length of a shortest $u-v$ path in G. The $\textit{diameter}$ of a graph G, denoted by diam(G), is the greatest distance between two vertices of G.

Recall that the $\textit{join}$ of two graphs $G_{1}$ and $G_{2}$, which is denoted by $G=G_{1}\vee G_{2}$, has the vertex set $V(G)=V(G_{1})\cup V(G_{2})$ and the edge set $E(G)=E(G_{1})\cup E(G_{2})\cup \{ uv | u\in V(G_{1}), v\in V(G_{2}) \}$. For example, $K_{1} \vee P_{n}$ is the $\textit{fan}$ $F_{n}$, $K_{1 }\vee C_{n}$ is the $\textit{wheel}$$W_{n}$, and the $\textit{friendship graph}$$Fr_{n}$ where $n = 2m+ 1$, is the graph obtained by joining $K_{1}$ to the m disjoint copies of $K_{2}$. For two arbitrary graphs G and H, the $\textit{corona product}$ of G and H to be the graph $G\odot H$ is obtained by taking one copy of G and |V(G)| copies of H by joining each vertex of i-th copy of H to the i-th vertex of G where $1\le i\le |V(G)|$.

In this paper, we show that the associated decision problem for the signed Italian domination is $\mathbf {NP}$-complete for the bipartite graphs. we obtain a probabilistic bound for the signed Italian domination number. Also we present sharp bounds on the signed Italian domination number of trees and in the end, we determine the signed Italian domination number of some graph operations. In addition, we determine the signed Italian domination number special classes of graphs including fans, wheels, and friendship graphs.

2 Complexity result

In this section, we present the $\mathbf {NP}$-complete result for the signed Italian domination problem in bipartite graphs.

SIGNED ITALIAN DOMINATING FUNCTION(SIDF)

$\mathbf {Instance:}$ Graph $G=(V,E)$, positive integer $k\le |V|$.

$\mathbf {Question:}$ Does G have a signed Italian dominating function of weight at most k?

We will show that this problem is $\mathbf {NP}$-complete by reducing the special case of Exact Cover by 3-sets $\mathbf {(X3C)}$ to which we refer as $\mathbf {X3C3}$. The $\mathbf {NP}$-completeness of $\mathbf {X3C3}$ was proven in 2008 by Hickey et al. [3].

X3C3

$\mathbf {Instance:}$ A set of elements X with $|X|=3q$ and a collection C of $m=3q$, 3-element subsets of X such that each element appears in exactly 3 elements of C.

$\mathbf {Question:}$ Is there a sub-collection $C^{'}$ of C such that every element of X appears in exactly one element of $C^{'}$?

Fig. 1

NP-completeness of signed Italian for bipartite graphs

Theorem 2.1

SIDF is NP-complete for bipartite graphs.

Proof

Since we can check in polynomial time that a function $f:V\rightarrow \{-1,1,2\}$ has weight at most k and is a signed Italian dominating function, then SIDF is a member of $\mathcal {N}\mathcal {P}$. Now let us show how to transform any instance of X3C3 into an instance G of SIDF, so that one of them has a solution if and only if the other one has a solution. Let $X=\{x_{1},x_{2},\ldots ,x_{3q}\}$ and $C=\{C_{1},C_{2},\ldots ,C_{3q}\}$ be an arbitrary instance of X3C3.

For each $x_{i}\in X$, we build a connected graph $H_{i}$ obtained from a cycle $C_{6}:v_{1}^{i}-v_{2}^{i}-v_{3}^{i}-v_{4}^{i}-v_{5}^{i}-v_{6}^{i}-v_{1}^{i}$ by adding edges $v_{2}^{i}v_{5}^{i}$ and $v_{3}^{i}v_{6}^{i}$. Let $W=\{v_{1}^{1},v_{1}^{2},\ldots ,v_{1}^{3q}\}$. For each $C_{j}\in C$, we build a connected graph $K_{j}$ obtained from two stars $K_{1,2}$ with centers $y_{j}$, $z_{j}$ and a path $P_{3}:y_{j}-c_{j}-z_{j}$. Let $A=\{c_{1},c_{2},\ldots ,c_{3q}\}$. Now to obtain a graph G, we add edges $c_{j}v_{1}^{i}$ if $x_{i}\in C_{j}$ (see Fig. 1). Clearly, G is a bipartite graph and set $k=10q$.

Suppose that the instance X, C of X3C3 has a solution $C^{'}$. We construct a signed Italian dominating function f on G of weight k. We assign the value 2 to all ${y_{j}}^ {,}$s, ${z_{j}}^ {,}$s, ${v^{i}_{3}}^ {,}$s and ${v^{i}_{5}}^ {,}$s, the value 1 to all ${v^{i}_{4}}^ {,}$s and the value − 1 to all ${v^{i}_{1}}^ {,}$s, ${v^{i}_{2}}^ {,}$s, ${v^{i}_{6}}^ {,}$s and leaves of G. For every $c_{j}$, assign value 2 if $C_{j}\in C^{'}$ and value 1 if $C_{j}\notin C^{'}$. Note that since $C^{'}$ exists, its cardinality is precisely q and so the number of ${c_{j}}^ {,}$s with weight 2 is q, having disjoint neighborhoods in W. Since $C^{'}$ is a solution for X3C3, every vertex in W is adjacent to vertex assigned a 2. Hence, it is straightforward to see that f is a signed Italian dominating function with weight $f(V)=8(3q)+3q+2q+2q-7(3q)=10q=k$.

Conversely, suppose that G has a signed Italian dominating function with weight at most k. Among all such functions, let g be one that assigns small values to the leaves of G and ${v^{i}_{1}}^ {,}$s. If $g(y_{j})=-1$ for some $1\le j\le 3q$, then every leaves adjacent to $y_{j}$ have label 2. Now we define $g^{'}:V(G)\rightarrow \{-1,1,2\}$ such that $g^{'}(y_{j})=2$, $g^{'}(x_{1})=-1$ for a leaf $x_{1}$ adjacent to $y_{j}$, $g^{'}(x_{2})=1$ for another leaf $x_{2}$ adjacent to $y_{j}$ and $g^{'}=g$ for remaining vertices of G. Thus $g^{'}$ is a signed Italian dominating function such that $w(g^{'})\lneq w(g)$, which is a contradiction and so $g(y_{j})>0$ for $1\le j\le 3q$. With the similar reasoning, we conclude that $g(z_{j})>0$ for $1\le j\le 3q$.

Next we shall show that $g(c_{j})>0$ for $1\le j\le 3q$. If $g(c_{j})=-1$ for some j, then $g(y_j)\ge 0$. If $g(y_j)=1$. then every two leaves adjacent to $y_j$ have label 1 and if $g(y_j)=2$, then at least one of leaf adjacent to $y_{j}$ has label 1 under g. In any cases we conclude that there exists a leaf in neighbor set of $y_{j}$ with label 1 under g. This fact is true for the vertex $z_j$. Now we define $g^{'}:V(G)\rightarrow \{-1,1,2\}$ such that $g^{'}(c_{j})=1$, $g^{'}(y_{j})=g^{'}(z_{j})=2$, $g^{'}(x)=-1$ for any leaf x of $y_{j}$ and $z_{j}$, and $g^{'}=g$ for remaining vertices of G. Thus $g^{'}$ is a signed Italian dominating function such that $w(g^{'})\le w(g)$, and the weight of leaves under $g^{'}$ is less than the weight of leaves under g, which is a contradiction with choosing the function g. So $g(c_{j})>0$. Therefore every support vertex of G is assigned a 2 and every leaf of G is assigned a − 1.

Finally, we shall show that $g(v^{i}_{1})=-1$ for $1\le i\le 3q$ and conclude that $g(V(H_{i}))\ge 2$. If $g(v^{i}_{1})>0$ for some $1\le i\le 3q$, then define $g^{'}:V(G)\rightarrow \{-1,1,2\}$ such that $g(v^{i}_{1})=g(v^{i}_{2})=g(v^{i}_{6})=-1$, $g(v^{i}_{3})=g(v^{i}_{5})=2$, $g(v^{i}_{4})=1$, $g(c_{j})=2$ for q of ${j}^ {,}$s where $1\le j\le 3q$ and $g^{'}=g$ for remaining vertices of G. Thus $g^{'}$ is a signed Italian dominating function such that $w(g^{'})\lneq w(g)$, which is a contradiction. In another case, we conclude that $g(v^{i}_{1})=-1$ for $1\le i\le 3q$ and $g(V(H_{i}))\ge 2$. Now assume that $r=|V_{2}\cap c_{j}|$, then $2r+3q-r+2(3q)\le k=10q$ and so $r\le q$. On the other hand, if define $T=\{(v^{i}_{1},c_{j})\ |\ v^{i}_{1}\sim c_{j} \ \text {and} \ g(c_{j})=2\}$, then

$$\begin{aligned} \underbrace{3+3+\cdots +3}_\text {r}\ge |T|\ge \underbrace{1+1+\cdots +1}_\text {3q}, \end{aligned}$$

hence $r\ge q$ and consequently $r=q$. Now since each $c_{j}$ has exactly three neighbors in W, we conclude that $C^{'}=\{C_{j}:g(c_{j})=2\}$ is an exact cover for C. $\square$

3 Probabilistic bound

For the probabilistic methods, we follow [7]. Analogously to some results of [7], we obtain a probabilistic bound for the signed Italian domination number.

Theorem 3.1

For any graph G with $\delta \ge 1$,

$$\begin{aligned} \gamma _{sI}(G)\le n\left( 2-\frac{2\hat{\delta }\tilde{d}_{0.5}}{{(1+\hat{\delta })^{1+\frac{1}{\hat{\delta }}}{{\tilde{d}_{0.5}}^{1+\frac{1}{\hat{\delta }}}}}}\right) , \end{aligned}$$

where $\hat{\delta }=\lfloor {0.5}\delta \rfloor$ and $\tilde{d}_{0.5}=\left( {\begin{array}{c}\delta {'}+1\\ \lceil {0.5}\delta {'}\rceil \end{array}}\right)$ such that $\delta ^{'}=\delta$ if $\delta$ is odd and $\delta ^{'}=\delta +1$ if $\delta$ is even.

Proof

Let A be a set formed by independent choice of vertices of G, where each vertex is selected with the probability

$$\begin{aligned} p=1-\frac{1}{(1+\hat{\delta })^\frac{1}{\hat{\delta }}{{\tilde{d}_{0.5}}^\frac{1}{\hat{\delta }}}}. \end{aligned}$$

For $m\ge 0$, let $B_{m}$ be the set of vertices $v\in V (G)$ dominated by exactly m vertices of A such that $N[v]\cap A= m\le \lceil {0.5}d_{v}\rceil$. Now form the set B by selecting $\lceil {0.5}d_{v}\rceil -m+1$ vertices from N[v] that are not in A for each vertex $v\in B_{m}$. We set $D=A\cup B$. Assume that $f:V(G)\rightarrow \{-1,1,2\}$ is a function such that all vertices in A and B are labeled by 2 and 1, respectively and all other vertices by − 1. It is obvious that $f(V(G))=3|A|-2|B|-n$ and f is a signed Italian domination function. The expectation of f(V(G)) is

$$\begin{aligned} E[f(V(G))]&=3E[|A|]+2E[|B|]-n\\&\le 3\sum _{i=1}^{n}p(v_{i}\in A)+2\sum _{i=1}^{n}\sum _{m=0}^{\lceil {0.5}d_{i}\rceil }(\lceil {0.5}d_{i}\rceil -m+1)p (v_{i}\in B_{m})-n\\&=3pn+2\sum _{i=1}^{n}\sum _{m=0}^{\lceil {0.5}d_{i}\rceil }(\lceil {0.5}d_{i}\rceil -m+1)\left( {\begin{array}{c}d_{i}+1\\ m\end{array}}\right) p^{m}(1-p)^{d_{i}+1-m}-n\\&\le 3pn+2\sum _{i=1}^{n}\max _{d_{i}\ge \delta }f(d_{i},p)-n, \end{aligned}$$

where $f(d,p)=\sum _{m=0}^{\lceil {0.5}d\rceil }(\lceil {0.5}d\rceil -m+1)\left( {\begin{array}{c}d+1\\ m\end{array}}\right) p^{m}(1-p)^{d+1-m}$ for any $d\ge \delta \ge 2$. By Lemma 1 [2], $\max _{d\ge \delta }f(d,p)\in \{f(\delta ,p),f(\delta +1,p)\}$ and so $\max _{d\ge \delta }f(d,p)= f(\delta ^{'},p)$. Therefore

$$\begin{aligned} E[f(V(G))]\le 3np+2n\sum _{m=0}^{\lceil {0.5}\delta ^{'}\rceil }(\lceil {0.5}\delta ^{'}\rceil -m+1)\left( {\begin{array}{c}\delta {'}+1\\ m\end{array}}\right) p^{m}(1-p)^{\delta ^{'}+1-m}-n. \end{aligned}$$

Since $(\lceil {0.5}\delta ^{'}\rceil -m+1)\left( {\begin{array}{c}\delta {'}+1\\ m\end{array}}\right) \le \left( {\begin{array}{c}\delta {'}+1\\ m\end{array}}\right) \left( {\begin{array}{c}\lceil {0.5}\delta {'}\rceil \\ m\end{array}}\right)$, then we obtain

$$\begin{aligned} E[f(V(G))]&\le 3np+2n\sum _{m=0}^{\lceil {0.5}\delta ^{'}\rceil }(\lceil {0.5}\delta ^{'}\rceil -m+1)\left( {\begin{array}{c}\delta {'}+1\\ m\end{array}}\right) p^{m}(1-p)^{\delta ^{'}+1-m}-n\\&=3np+2n\left( {\begin{array}{c}\delta {'}+1\\ \lceil {0.5}\delta {'}\rceil \end{array}}\right) (1-p)^{\delta ^{'}-\lceil {0.5}\delta {'}\rceil +1} \sum _{m=0}^{\lceil {0.5}\delta ^{'}\rceil }\left( {\begin{array}{c}\lceil {0.5}\delta ^{'}\rceil \\ m\end{array}}\right) p^{m}(1-p)^{\lceil {0.5}\delta ^{'}\rceil -m}-n\\&=3np+2n{\tilde{d}_{0.5}}(1-p)^{\delta ^{'}-\lceil {0.5}\delta ^{'}\rceil +1}-n. \end{aligned}$$

Taking into account that $\delta {'}-\lceil {0.5}\delta {'}\rceil =\lfloor {0.5}\delta {'}\rfloor =\lfloor {0.5}\delta \rfloor =\hat{\delta }$, we have

$$\begin{aligned} E[f(V(G))]&\le 3np+2n{\tilde{d}_{0.5}}(1-p)^{\hat{\delta }+1}-n\\&\le 2n\left( 1-\frac{\hat{\delta }\tilde{d}_{0.5}}{{(1+\hat{\delta })^{1+\frac{1}{\hat{\delta }}}{{\tilde{d}_{0.5}}^{1+\frac{1}{\hat{\delta }}}}}}\right) . \end{aligned}$$

$\square$

4 Tree

In this section, we present sharp bounds on the signed Italian domination number of trees. In first, we show that there exist graphs with signed Italian domination number which are negative.

Proposition 4.1

For every integer $k\ge 1$, there exists a tree T of order $4k+3$ such that $\gamma _{sI}(T)\le -\,k$.

Proof

For every integer $k\ge 1$, let T be the tree obtained from $K_{1,2}$ with center vertex $x_{0}$ and k copies of graph $K_{1,3}$ with centers $x_{1}, x_{2}, \cdots , x_{k}$, where $x_{i}$ is adjacent to $x_{i+1}$ for $0\le i \le k-1$. Define the function $f:V(T)\rightarrow \{-1, 1, 2\}$ such that $f(x_{i})=2$ for each $0\le i \le k$ and $f(y)=-1$ for each leaf of T. It is straightforward to check that f is a SIDF on T of weight $2(k+1)-3k-2=-k$. Therefore $\gamma _{sI}(T_{k})\le -k$. $\square$

Remark 4.2

Let G be a graph and f be a signed Italian domination. Hence there exists a signed Italian domination g with $w(g)\le w(f)$ such that for any support vertex v, we have $v\notin V_{-1}^{g}$. Since if v is support vertex with $f(v)=-1$, then for any $u_{i}$ adjacent to v, we have $f(u_{i})=2$. Consider the leaf u adjacent to v and define $g:V(G)\rightarrow \{-1,1,2\}$ by $g(v)=2$, $g(u)=-1$ and $g(x)=f(x)$ for each vertex $x\in V(G)\setminus \{v,u\}$. Clearly, again g is a signed Italian domination function and $w(g)\le w(f)$.

Now based on the above remark, the following result is obvious.

Proposition 4.3

For $r\ge s\ge 1$,

$$\begin{aligned} \gamma _{sI}(DS_{r,s})=\left\{ \begin{array}{ll} 2 &{}\quad \text {if }s=r=1,\\ 1 &{}\quad \text {if }s=1 \ r>1\hbox { is even},\\ 0 &{}\quad \text {if }s=1 \ r>1\hbox { is odd},\\ 0 &{}\quad \text {if }s>1 \ s,r\hbox { are even},\\ -1 &{}\quad \text {if }s>1 \ s\hbox { is odd and }r\hbox { is even},\\ -2 &{}\quad \text {if }s>1 \ s,r\hbox { are odd}. \end{array} \right. \end{aligned}$$

Now we present a sharp bound on the signed Italian domination number in Trees. In first, we introduce some notation for convenience.

Let $V_{l}=\{v\in V(T) \ | \ v\ is\ a\ leaf\}$, $V_{s}=\{v\in V(T) \ | \ v\ is\ a\ support\ vertex \}$ and $V_{w}=V(T)\setminus (V_{l}\cup V_{s})$.

For any tree T, let $F_{T}$ be the tree obtained from T by adding $2deg(v)+1$ pendant edges to each vertex $v\in V(T)$. Assume that $\mathcal {T}=\{ F_{T} \ | \ T \ is \ tree \}$.

Theorem 4.4

If T be a tree of order $n\ge 2$, then $\gamma _{sI}(T)\ge \frac{-n+4}{2}$ with equality holds if and only if $T\in \mathcal {T}$.

Proof

We proceed by induction on $n\ge 2$. If $n=2$, then $T=K_{2}$, $\gamma _{sI}(K_{2})=1=\frac{-n+4}{2}$. If $n=3$, then $T=P_{3}$, $\gamma _{sI}(T)=2>\frac{-n+4}{2}$. Let $n\ge 4$ and suppose that the statement holds for all trees of order less than n. Let T be tree of order n. If $diam(T)=2$, then T is a star and by Proposition 4 in [6], we have $\gamma _{sI}(T)\ge \frac{-n+4}{2}$. If $diam(T)=3$, then T is a double star $DS_{r,s}$ with $r\ge s\ge 1$ and by Proposition 4.3, we have $\gamma _{sI}(T)\ge \frac{-n+4}{2}$ with equality if and only if $T=DS_{3,3}$. Therefore assume that $diam(T)\ge 4$. Let $f=(V_{-1},V_{1},V_{2})$ be a $\gamma _{sI}$-function of T.

At first, suppose that $V_{-1}$ is not an independent set. If $u,v\in V_{-1}$ are adjacent vertices, then u and v are not leaves. Hence if $T_{1}$ and $T_{2}$ are two trees obtained from T by removing the edge uv, then $T_{1}$ and $T_{2}$ are nontrivial and the function $f_{i}=f|_{T_{i}}$ is a SIDF of $T_{i}$ for each $i\in \{1,2\}$. Using the inductive hypothesis on $T_{1}$ and $T_{2}$ with the fact that $w(f)=w(f_{1})+w(f_{2})$ we obtain

$$\begin{aligned} \gamma _{sI}(T)=w(f_{1})+w(f_{2})\ge \frac{-|V(T_{1})|+4}{2}+\frac{-|V(T_{2}|+4}{2}>\frac{-n+4}{2}, \end{aligned}$$

and result is obtained. Suppose that $V_{-1}$ is an independent set. Consider the following cases:

$\varvec{Case\ 1}.$ $(V_{w}\cup V_{s})\cap V_{-1}\ne \emptyset$.

By Remark 4.2, we can assume that v is not support vertex i.e $v\in V_{w}$. Suppose that $T_{1},T_{2},\cdots ,T_{r}$ are the components of $T\setminus v$ and let $f_{i}$ be the restriction of f on $T_{i}$ for $1\le i\le r$. Since $T_{i}$’s are nontrivial for any $1\le i\le r$, then by inductive hypothesis we have

$$\begin{aligned} \gamma _{sI}(T)&=\sum _{i=1}^{r}w(f_{i})+f(v)\ge \sum _{i=1}^{r} \frac{-|V(T_{i})|+4}{2}+f(v)\\&\ge \frac{-n+4}{2}+\frac{1+4(r-1)}{2}-1>\frac{-n+4}{2}. \end{aligned}$$

According to Case 1, we may assume that all non-leaf vertex of T have positive weight under f.

$\varvec{Case \ 2}.$ $(V_{w}\cup V_{s})\cap V_{-1}=\emptyset$.

$\varvec{Subcase \ 1}.$ $(V_{w}\cup V_{s})\cap V_{1} \ne \emptyset$.

Let $v\in V_{s}$ with $f(v)=1$. Hence any leaf adjacent to v must be assigned 1 or 2 under f. Let $T_{1},T_{2},\cdots ,T_{r}$ be the components of $T\setminus v$ of order at least two and let $v_{i}\in V(T_{i})$ be a vertex adjacent to v for each i. Then we have $f(v_{i})\ge 1$ for each i ( by Case 1). If $f(v_{i})=1$ for some i, say $i=1$, then let $F_{1}$ and $F_{2}$ be the components of $T\setminus vv_{1}$ containing $v_{1}$ and v, respectively. Define $g:V(F_{1})\rightarrow \{ -1,1,2\}$ by $g(v_{1})=f(v_{1})+1$ and $g(x)=f(x)$ for $x\in V(F_{1})-\{v_{1}\}$. Clearly, g is a SIDF of $F_{1}$ and the function $f_{2}=f|_{F_{2}}$ is a SIDF of $F_{2}$. By inductive hypothesis we deduce that

$$\begin{aligned} \gamma _{sI}(T)&=w(g)+w(f_{2})-1\\&\ge \frac{-|V(F_{1})|+4}{2}+ \frac{-|V(F_{2})|+4}{2}-1\\&\ge \frac{-n+4}{2}+\frac{4}{2}-1>\frac{-n+4}{2}. \end{aligned}$$

Assume that $f(v_{i})=2$ for each i. Let $F_{1}$ and $F_{2}$ be the components of $T\setminus vv_{1}$ containing $v_{1}$ and v respectively. Let $F^{'}$ be the tree obtained from $F_{1}$ by adding a new vertex $v^{'}$ attached at $v_{1}$ by an edge $v_{1}v^{'}$. Define $g:V(F_{1}^{'})\rightarrow \{-1,1,2\}$ by $g(v^{'})=1$ and $g(x)=f(x)$ for $x\in V(F_{1}^{'})\setminus \{v^{'}\}$. Clearly, g is a SIDF of $F_{1}^{'}$ and the function $f_{2}=f|_{F_{2}}$ is a SIDF of $F_{2}$. Again by inductive hypothesis for trees $F_{1}^{'}$ and $F_{2}$ we conclude that

$$\begin{aligned} \gamma _{sI}(T)&=w(g)+w(f_{2})-1\\&\ge \frac{-|V(F_{1}^{'})|+4}{2}+\frac{-|V(F_{2})|+4}{2}-1\\&\ge \frac{-(n+1)+8}{2}-1>\frac{-n+4}{2}. \end{aligned}$$

Regarding above cases, we may assume that $f(v)=2$ for each non-leaf vertex, v, of T.

$\varvec{Subcase\ 2}.$ $(V_{w}\cup V_{s})\cap V_{2} \ne \emptyset$

At first, suppose that $v\in V_{w}$. Let us recall from the foregoing that all neighbors of v belong to $V_{2}$. Consider the forest $T\setminus v$ by adding $deg(v)-1$ edges between vertices of N(v) in $T\setminus v$ so that the resulting graph $T^{*}$ is a tree. Clearly $f^{*}=f|_{T\setminus v}$ is a SIDF on $T^{*}$. Using the fact that $n=|V(T^{*})|+1$ and $w(f)=w(f^{*})+2$ and by applying inductive hypothesis on $T^{*}$, we have

$$\begin{aligned} \gamma _{sI}(T)=w(f^{*})+2\ge \frac{-|V(T^{*})|+4}{2}+2>\frac{-n+4}{2}. \end{aligned}$$

Obviously, no support vertex can have all its leaves in $V\setminus V_{-1}$. Now let v be a support vertex and $u_1,u_2,\cdots ,u_s$ its leaves.

Let $f(u_{i})=1$, $f(u_{j})=-1$ for some i, j and $T^{'}=T\setminus \{u_{i},u_{j}\}$. The function f restricted to $T^{'}$ is a SIDF of $T^{'}$, and inductive hypothesis implies that

$$\begin{aligned} \gamma _{sI}(T)=w(f|_{T^{'}})\ge \frac{-(n-2)+4}{2}>\frac{-n+4}{2}. \end{aligned}$$

Let $f(u_{i})=2$, $f(u_{j})=-1$ for some i, j, and $T^{'}$ be a tree obtained from $T\setminus u_{j}$. Clearly the function g defined on $T^{'}$ by $g(u_{i})=1$ and $g(x)=f(x)$ otherwise is a SIDF of $T^{'}$. By the inductive hypothesis we have

$$\begin{aligned} \gamma _{sI}(T)=w(f)=w(g)\ge \frac{-(n-1)+4}{2}>\frac{-n+4}{2}. \end{aligned}$$

Finally, by above cases, we may assume that every vertex of T is either a leaf or a support vertex and all leaves of T belong to $V_{-1}$. Recall that all support vertices belong to $V_{2}$. For every support vertex v, let $l_{v}$ be the number of leaves in $N_{T}(v)$. Let $T^{'}$ be the tree obtained from T by removing all leaves of T and let $n^{'}=|V(T^{'})|$. Since for every support vertex v, $f[v]\ge 1$ we must have $l_{v}\le 2deg_{T^{'}}(v)+1$. Note that $\sum _{v\in V(T^{'})}l_{v}\le \sum _{v\in V(T^{'})}(2deg_{T^{'}}(v)+1)=5n^{'}-4$. Using the facts that $n=n^{'}+\sum _{v\in V(T^{'})}l_{v}$, and $\gamma _{sI}(T)=2n^{'}-\sum _{v\in V(T^{'})}l_{v}$, one can easily check that

$$\begin{aligned} \gamma _{sI}(T)=2n^{\prime }-\sum _{v\in V(T^{\prime })}l_{v}\ge \frac{-(n^{\prime }+\sum _{v\in V(T^{\prime })}l_{v})+4}{2}=\frac{-n+4}{2}. \end{aligned}$$

If further $\gamma _{sI}(T)=\frac{-n+4}{2}$, then we must have equality throughout the previous inequality chain which implies in particular that $l_{v}=2deg(v)+1$ for every $v\in V(T^{'})$ and therefore $T\in \mathcal {T}$.

Conversely, if $T\in \mathcal {T}$, then define the function $g:V(T)\rightarrow \{-1,1,2\}$ such that assigns $-1$ to all leaves and 2 to all support vertices. Thus g is a SIDF of T and so $\gamma _{sI}(T)\le \frac{-n+4}{2}$, this implies that $\gamma _{sI}(T)= \frac{-n+4}{2}$, hence the proof is complete. $\square$

5 Operations on graphs

In this section, we express signed Italian domination number of some graph operations.

Proposition 5.1

If $G_{1}$ and $G_{2}$ are two graphs such that $\gamma _{sI}(G_{1}) \ge 0$ and $\gamma _{sI}(G_{2}) \ge 0$, then $\gamma _{sI}(G_{1}\vee G_{2}) \le \gamma _{sI}(G_{1})+\gamma _{sI}(G_{2})$.

Proof

Let $f_{1}$ be a $\gamma _{sI}$-function on $G_{1}$ and $f_{2}$ be a $\gamma _{sI}$-function on $G_{2}$. Define the function $f: V(G_{1}\vee G_{2})\rightarrow \{-1, 1, 2\}$ by $f(v)=f_{1}(v)$ for each $v\in V(G_{1})$ and $f(v)=f_{2}(v)$ for each $v\in V(G_{2})$. Hence for each $v\in V(G_{1})$, $f(N_{G_{1}\vee G_{2}}[v])=f(N_{G_{1}}[v])+w(f_{2})\ge 1$. Similarly, for each $v\in V(G_{2})$, $f(N_{G_{1}\vee G_{2}}[v])=f(N_{G_{2}}[v])+w(f_{1})\ge 1$. Thus f is a SIDF on $(G_{1}\vee G_{2})$, and $\gamma _{sI}(G_{1}\vee G_{2})\le w(f)= w(f_{1}) + w(f_{2})=\gamma _{sI}(G_{1})+\gamma _{sI}( G_{2})$. $\square$

Proposition 5.2

Let $m \ge 2$ be an integer and $n=2m+1$. If $G=Fr_{n }=K_{1 }\vee (mK_{2})$, then $\gamma _{sI}(Fr_{n})=1$.

Proof

Suppose that $V(Fr_{n}) = \{x\} \cup \{y_{i},z_{i} \ | \ 1 \le i \le m\}$ and $E(Fr_{n})= \{xy_{i}, xz_{i} \ | \ 1 \le i \le m \} \cup \{y_{i}z_{i} \ | \ 1\le i \le m\}$. Since $\Delta (Fr_{n}) = n-1$, then Theorem 1 in [6] implies that $\gamma _{sI}(Fr_{n})\ge 1.$

Now define the function $f:V(Fr_{n}) \rightarrow \{ -1,1,2 \}$ by $f(x)=1$, $f(x_{i})=1$ for $1\le i\le m$, and $f(y_{i})=-1$ for $1\le i\le m$. It is clear that f be a SIDF on $Fr_{n}$ of weight 1. Hence $\gamma _{sI}(Fr_{n})\le 1$ and consequently, $\gamma _{sI}(Fr_{n})=1$. $\square$

Proposition 5.3

Let $W_{n} = K_{1} \vee C_{n}$ be a wheel of order $n+1$. Then $\gamma _{sI}(W_{4}) = 2$ and $\gamma _{sI}(W_{n}) = 1$ for each $n\ne 4$.

Proof

Suppose that $V(W_{n})= \{ v_{0},\cdots , v_{n}\}$ and $E(W_{n})= \{v_{0}v_{i} \ | \ 1 \le i\le n \}\cup \{v_{1}v_{2},\cdots ,v_{n}v_{1}\}$. The result is trivial to check for $n\le 4$. Assume that $n\ge 5$, since $\Delta (W_{n})=n$, then Theorem 1 in [6] implies that $\gamma _{sI}(W_{n})\ge 1$.

To complete the proof, it is sufficient to provide a signed Italian domination function of weight 1 on $W_{n}$ for each $n\ne 4$. First, assume that n is odd. Then define the function $f:V(W_{n})\rightarrow \{-1,1,2\}$ by

$$\begin{aligned} f(v_{i})=\left\{ \begin{array}{ll} 2 &{}\quad \text {if }i=0,\\ 1 &{}\quad \text {if }i\equiv 0 \pmod {2},\\ -1 &{}\quad \text {if }i\equiv 1 \pmod {2}. \end{array} \right. \end{aligned}$$

Now assume that n is even such that $n\equiv 0\pmod {3}$. Then define the function $f:V(W_{n})\rightarrow \{-1,1,2\}$ by

$$\begin{aligned} f(v_{i})=\left\{ \begin{array}{ll} 1 &{}\quad \text {if }i=0,\\ 2 &{}\quad \text {if } i\ge 1,\ i\equiv 0 \pmod {3},\\ -1 &{}\quad \text {o.w.} \end{array} \right. \end{aligned}$$

Next assume that n is even such that $n\equiv 1\pmod {3}$. Then define the function $f:V(W_{n})\rightarrow \{-1,1,2\}$ by

$$\begin{aligned} f(v_{i})=\left\{ \begin{array}{ll} 2 &{}\quad \text {if }i=0,\\ 1 &{}\quad \hbox { }\ i\in \{n-4,n-1,n\}\\ 2 &{}\quad \text {if } 1\le i\le n-7,\ i\equiv 0 \pmod {3},\\ -1 &{}\quad \text {o.w.} \end{array} \right. \end{aligned}$$

Finally, assume that n is even such that $n\equiv 2\pmod {3}$. Then define the function $f:V(W_{n})\rightarrow \{-1,1,2\}$ by

$$\begin{aligned} f(v_{i})=\left\{ \begin{array}{ll} 2 &{}\quad \text {if }i=0,\\ 1 &{}\quad \hbox { }\ i\in \{n-2,n\},\\ 2 &{}\quad \text {if }1\le i\le n-5,\ i\equiv 0 \pmod {3},\\ -1 &{}\quad \text {o.w.} \end{array} \right. \end{aligned}$$

In any cases, one can easily to check that f is a SIDF on $W_{n}$ of weight 1. Therefore in any cases, we have a SIDF on $W_{n}$ of weight 1 and so $\gamma _{sI}(W_{n})\le 1$ for each $n\ne 4$ which proof is complete. $\square$

Proposition 5.4

Let $F_{n} = K_{1}\vee P_{n}$ be a fan of order $n+1$. Then $\gamma _{sI}(F_{n})=1$.

Proof

Let $V(F_{n}) = \{v_0, v_1,\cdots , v_n\}$ and $E(F_{n})= \{v_{0}v_{i}\ | \ 1\le i \le n\}\cup \{v_1v_2,\cdots , v_{n-1}v_{n}\}$. The result is trivial to check for $n\le 4$. Since $\Delta (F_{n})=n$, then Theorem 1 in [6] implies that $\gamma _{sI}(F_{n})\ge 1$.

To complete the proof, it is sufficient to provide a signed Italian domination function of weight 1 on $F_{n}$. First, assume that n is odd. Then define the function $f:V(F_{n})\rightarrow \{-1,1,2\}$ by

$$\begin{aligned} f(v_{i})=\left\{ \begin{array}{ll} 2 &{}\quad \text {if }i=0,\\ 1 &{}\quad \text {if }i\equiv 0 \pmod {2},\\ -1 &{}\quad \text {if }i\equiv 1 \pmod {2}. \end{array} \right. \end{aligned}$$

Now assume that n is even such that $n\equiv 0\pmod {3}$. Then define the function $f:V(F_{n})\rightarrow \{-1,1,2\}$ by

$$\begin{aligned} f(v_{i})=\left\{ \begin{array}{ll} 1 &{}\quad \text {if }i=0,\\ 2 &{}\quad \text {if } i\ge 1,\ i\equiv 2 \pmod {3},\\ -1 &{}\quad \text {o.w.} \end{array} \right. \end{aligned}$$

Next assume that n is even such that $n\equiv 1\pmod {3}$. Then define the function $f:V(F_{n})\rightarrow \{-1,1,2\}$ by

$$\begin{aligned} f(v_{i})=\left\{ \begin{array}{ll} 2 &{}\quad \text {if }i=0,\\ 1 &{}\quad \hbox { }\ i\in \{n-5, n-2, n\},\\ 2 &{}\quad \text {if } 2\le i\le 3k+2,\ 0\le k\le \frac{n-10}{3},\\ -1 &{}\quad \text {o.w.} \end{array} \right. \end{aligned}$$

Finally, assume that n is even such that $n\equiv 2\pmod {3}$. Then define the function $f:V(F_{n})\rightarrow \{-1,1,2\}$ by

$$\begin{aligned} f(v_{i})=\left\{ \begin{array}{ll} 2 &{}\quad \text {if }i=0,\\ 1 &{}\quad \hbox { }\ i\in \{n-3,n-1\},\\ 2 &{}\quad \text {if } 2\le i\le 3k+2,\ 0\le k\le \frac{n-8}{3},\\ -1 &{}\quad \text {o.w.} \end{array} \right. \end{aligned}$$

In any cases, one can easily to check that f is a SIDF on $F_{n}$ of weight 1. Therefore in any cases, we have a SIDF on $F_{n}$ of weight 1 and so $\gamma _{sI}(F_{n})\le 1$. This completes the proof. $\square$

Now we present the signed Italian dominating function of the corona product graph of some special graphs.

Proposition 5.5

For two integer numbers $n,m>2$, $\gamma _{sI}(C_{n}\odot K_{m})=n$.

Proof

Let $G=C_{n}\odot K_{m}$ be a graph with vertices set V. We consider two following cases:

Case 1. Let m be even. Define the function $f:V\rightarrow \{-1,1,2\}$ by $f(v)=2$ for one vertex $v\in K_{m}$, $f(v)=-1$ for $\frac{m+2}{2}$ vertices of $K_{m}$, $f(v)=1$ for the remaining vertices of $K_{m}$ and $f(v)=2$ for each vertex of $C_{n}$. In this case, produce a SIDF of weight n and so $\gamma _{sI}(C_{n}\odot K_{m})\le n$.

Case 2. Let m be odd. Define the function $f:V\rightarrow \{-1,1,2\}$ by $f(v)=-1$ for $\frac{m+1}{2}$ vertices of $K_{m}$, $f(v)=1$ for the remaining vertices of $K_{m}$ and $f(v)=2$ for each vertex of $C_{n}$. In this case, produce a SIDF of weight n and so $\gamma _{sI}(C_{n}\odot K_{m})\le n$.

Now let f be a signed Italian domination function of G and ${K_{m}}^{i}$ be copy corresponding vertex $c_{i}$. Since $f[x]=w(K_{m}^{i})+f(c_{i})\ge 1$ for each vertex $x\in K_{m}^{i}$ and $c_{i}\in V(C)$, then $w(K_{m}^{i})\ge 1-f(c_{i})\ge -1$. If $w(K_{m}^{i})=-1$, then $f(c_{i})=2$. If $w(K_{m}^{i})=0$, then $f(c_{i})\ge 1$. If $w(K_{m}^{i})= 1$, then $f(c_{i})\ge 1$. If $w(K_{m}^{i})\ge 2$, then $f(c_{i})\ge -1$. In any case, $w(f)\ge n$. This is true for any signed Italian dominating function of G. Therefore $\gamma _{sI}(G)=\min \{f \ | \ f\ is\ a\ SIDF\ of\ G \}\ge n$. Hence $\gamma _{sI}(C_{n}\odot K_{m})=n$. $\square$