An Italian dominating function (IDF) on a graph G is a function \(f:V(G)\rightarrow \{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., \(\sum _{u\in N_G(v)}f(u)\ge 2\). For any function \(f:V(G)\rightarrow \{0,1,2\}\) and any pair of adjacent vertices with \(f(v) = 0\) and u with \(f(u) > 0\), the function \(f_{u\rightarrow v}\) is defined by \(f_{u\rightarrow v}(v)=1\), \(f_{u\rightarrow v}(u)=f(u)-1\) and \(f_{u\rightarrow v}(x)=f(x)\) whenever \(x\in V(G){\setminus }\{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\rightarrow v}\) is an IDF. The weight of f is \(\omega (f)=\sum _{v\in 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.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The following approach to protection of a graph was described by Cockayne et al. (2005). Suppose that one or more guards are stationed at some of the vertices of a simple graph G and that a guard at a vertex can deal with a problem at any vertex in its closed neighbourhood. Consider a function \(f: V(G)\longrightarrow \{0,1,2\}\) where f(v) is the number of guards at v, and let \(V_i=\{v\in V(G):\; f(v)=i\}\) for every \(i\in \{0,1,2\}\). We will identify a function f with the subsets \(V_0,V_1,V_2\) of V(G) associated with it, and so we will use the unified notation \(f(V_0,V_1, V_2)\) for the function and these associated subsets. The weight of f is defined to be \(\omega (f)=f(V(G))=|V_1|+2|V_2|\). Informally, we say that G is protected under f if there is at least one guard available to handle a problem at any vertex. Next we show some approaches to the protection of graphs. The functions in each approach protect the graph according to a certain strategy.
We assume that the reader is familiar with the basic concepts, notation and terminology of domination in graphs. If this is not the case, we suggest the textbooks (Haynes et al. 1998a, b). For the remainder of the paper, definitions will be introduced whenever a concept is needed.
Anzeige
A Roman dominating function (RDF) is a function \(f(V_0,V_1,V_2)\) such that for every vertex \(v\in V_0\) there exists a vertex \(u\in N_G(v)\cap V_2\), where \(N_G(v)\) denotes the open neighbourhood of v. The Roman domination number, denoted by \(\gamma _R(G)\), is the minimum weight among all RDFs on G. This concept of protection has historical motivation (Stewart 1999) and was formally proposed by Cockayne et al. (2004). A Roman dominating function with minimum weight \(\gamma _{_R}(G)\) on G is called a \(\gamma _{_R}(G)\)-function. A similar agreement will be assumed when referring to optimal functions (and sets) associated with other parameters used in the article.
A generalization of Roman domination, known as Italian domination, was introduced by Chellali et al. (2016) under the name of Roman \(\{2\}\)-domination. The concept was studied further in Henning and Klostermeyer (2017) and Klostermeyer and MacGillivray (2019). An Italian dominating function (IDF) on a graph G is a function \(f(V_0,V_1,V_2)\) satisfying that \(f(N_G(v))=\sum _{u\in N_G(v)}f(u)\ge 2\) for every \(v\in V_0\), i.e., \(f(V_0,V_1,V_2)\) is an IDF if \(N_G(v)\cap V_2\ne \emptyset \) or \(|N_G(v)\cap V_1|\ge 2\) for every \(v\in V_0\). The Italian domination number, denoted by \(\gamma _I(G)\), is the minimum weight among all IDFs on G. Since every \(\gamma _{_R}(G)\)-function is an IDF, \(\gamma _{_R}(G)\ge \gamma _{_I}(G)\).
For any function \(f(V_0, V_1, V_2)\) and any pair of adjacent vertices \(v\in V_0\) and \(u\in V_1\cup V_2\), the function \(f_{u\rightarrow v}\) is defined by \(f_{u\rightarrow v}(v)=1\), \(f_{u\rightarrow v}(u)=f(u)-1\) and \(f_{u\rightarrow v}(x)=f(x)\) whenever \(x\in V(G){\setminus }\{u,v\}\).
A vertex \(v\in V_0\) is said to be undefended under a function \(f(V_0, V_1, V_2)\) if \(N_G(v)\cap (V_1\cup V_2)=\emptyset \). A function \(f(V_0,V_1,V_2)\) is a weak Roman dominating function (WRDF) if for every vertex \(v\in V_0\) there exists \(u\in N(v)\cap (V_1\cup V_2)\) such that G does not have undefended vertices under \(f_{u\rightarrow v}\). The weak Roman domination number, denoted by \(\gamma _r(G)\), is the minimum weight among all WRDFs on G. This concept of protection was introduced by Henning and Hedetniemi (2003) and studied further in Chellali et al. (2014), Cockayne et al. (2003) and Valveny et al. (2019).
Anzeige
Notice that, every \(\gamma _{_I}(G)\)-function is a WRDF, which implies that \(\gamma _{_I}(G)\ge \gamma _{r}(G)\).
A secure dominating set is a dominating set S which satisfies that for every \(v\in V(G){\setminus } S\) there exists \(u\in S\cap N_G(v)\) such that \((S{\setminus } \{u\})\cup \{v\}\) is a dominating set as well. The secure domination number, denoted by \(\gamma _s(G)\), is the minimum cardinality among all secure dominating sets. Notice that S is a secure dominating set if and only if there exists a WRDF \(f(V_0,V_1,V_2)\) such that \(V_1=S\) and \(V_2=\emptyset \). Hence, \(\gamma _{s}(G)\ge \gamma _r(G)\). This concept of protection was introduced by Cockayne et al. (2005), and studied further in Merouane and Chellali (2015), Burger et al. (2008), Chellali et al. (2014), Cockayne et al. (2003), Klostermeyer and Mynhardt (2008) and Valveny and Rodríguez-Velázquez (2019).
Now, from the previous inequalities, we derive the following inequality chains.
In this article we introduce the study of secure Italian domination in graphs. We define a secure Italian dominating function (SIDF) to be an IDF \(f(V_0,V_1,V_2)\) which satisfies that for every vertex \(v\in V_0\) there exists \(u\in N_G(v)\cap (V_1\cup V_2)\) such that the \(f_{u\rightarrow v}\) is an IDF on G. In particular, whenever \(f_{u\rightarrow v}\) is an IDF, we will say that u is a moving neighbour of v. Obviously, if \(f(V_0,V_1,V_2)\) is an SIDF, then every vertex \(v\in V_0\) has at least one moving neighbour. The secure Italian domination number, denoted by \(\gamma _{I}^s(G)\), is the minimum weight among all SIDFs on G. In Fig. 1 we show two examples of \(\gamma _{I}^s(G)\)-functions.
Fig. 1
The labels in these graphs define \(\gamma _I^s(G)\)-functions
×
By definition of secure Italian domination number we immediately deduce the following inequalities.
The paper is structured as follows. In Sect. 2 we show that the general problem of finding the secure Italian domination number of a graph is NP-hard. In Sect. 3 we derive general bounds and discuss some extremal cases. In particular, we show that any non-empty graph G satisfies \(\max \{\gamma _2(G),\gamma _r(G)+1\}\le \gamma _I^s(G) \le \gamma (G) + \gamma _s(G)\). In Sect. 4 we obtain a formula for the secure Italian domination number of paths and cycles. Furthermore, we characterize all trees T satisfying \(\gamma _I^s(T) = \gamma (T) +1\) or \(\gamma _I^s(T) = \gamma (T) +2\). Finally, Sect. 5 is devoted to the study of join graphs.
2 NP-hardness
This section is devoted to prove that for any graph G of order n there exists a graph \(G'\) such that \(\gamma _{I}^s(G')=\gamma _{r}(G)+n\), showing that the problem of finding \(\gamma _{I}^s(G')\) is as difficult as the problem of finding \(\gamma _r(G)\). To begin with, we need to state the following lemma. Let L(G) denotes the set of all leaves in G.
Lemma 1
If G is a graph with set of leaves \(L(G)\ne \emptyset \), then there exists a \(\gamma _{I}^s(G)\)-function f such that \(f(v)=1\) for every \(v\in L(G)\).
Proof
Let f be a \(\gamma _{I}^s(G)\)-function, \(v\in L(G)\) and s the support of v. If \(f(v)=2\), then \(f(s)=0\), by the minimality of \(\omega (f)\). In such a case, \(f'=f_{v\rightarrow s}\) is a \(\gamma _{I}^s(G)\)-function with \(f'(v)=1\). Now, if \(f(v)=0\), then \(f(s)=2\) and s is a moving neighbour only of v. Hence, \(f''=f_{s\rightarrow v}\) is a \(\gamma _{I}^s(G)\)-function with \(f''(v)=1\). Therefore, the result follows. \(\square \)
Let G be a graph with vertex set \(V(G)=\{v_1,\dots , v_{n}\}\) and let H be a rooted graph. The rooted product of G and H is the graph \(G \circ H\) constructed from G and n copies \(H_1, H_2, \dots , H_{n}\) of H, by identifying \(v_i\) with the root vertex of \(H_i\) for every \(i\in \{1,\dots ,n\}\).
Theorem 2
For any graph G of order n, \(\gamma _I^s(G \circ K_2)= n + \gamma _r(G).\)
Proof
Let h be a \(\gamma _r(G)\)-function and \(h'\) the function defined on \(G\circ K_2\) in the way that \(h'(x)=h(x)\) if \(x \in V(G)\) and \(h'(x)=1\) otherwise. Since \(h'\) is an SIDF on \(G \circ K_2\), we conclude that \(\gamma _I^s(G \circ K_2)\le \omega (h')=n +\omega (h)=n+ \gamma _r(G).\)
We show that \(\gamma _I^s(G \circ K_2) \ge n + \gamma _r(G).\) Let \(f(V_0, V_1, V_2)\) be a \(\gamma _I^s(G \circ K_2)\)-function. By Lemma 1 we can assume that \(f(v)=1\) for every leaf v. Let \(g(W_0, W_1, W_2)\) be the restriction of f to V(G). That is, \(W_i = V_i \cap V(G)\) for \(i \in \{0,1,2\}\). Notice that \(W_0 = V_0\) and \(W_2 = V_2.\) We claim that g is a WRDF on G. We have to show that for every \(x \in W_0\) there exists \(y \in W_1 \cup W_2\) such that G does not have undefended vertex under \(g_{y \rightarrow x}\). We know that for every \(x \in V_0=W_0\) there exists \(y \in V_1 \cup V_2\) such that \(f_{y \rightarrow x}(V'_0, V'_1, V'_2)\) is an IDF on \(G \circ K_2\), and also the restriction of \(f_{y \rightarrow x}\) to V(G) equals \(g_{y \rightarrow x}\). Thus, y has to belong to \(W_1 \cup W_2\) and for every \(z \in V_0 {\setminus } \{x\}\) either \(|N_{G \circ K_2}(z) \cap V'_1|\ge 2\) or \(|N_{G \circ K_2}(z) \cap V'_2|\ge 1\), which implies that \(|N_{G}(z) \cap V'_1\cap V(G)|\ge 1\) or \(|N_{G}(z) \cap V'_2\cap V(G)|\ge 1\). Consequently, G does not have undefended vertex under \(g_{y \rightarrow x}\). Therefore, \(\gamma _I^s(G \circ K_2) = \omega (f) = |V_1|+2|V_2|= n+ |W_1|+2|W_2|=n+ \omega (g) \ge n + \gamma _r(G).\)\(\square \)
Our next result shows that we can use rooted product graphs to study the problem of finding the secure Italian domination number of a graph. In this case, the main tool is Theorem 2. It is well known that the weak Roman dominating set problem is an NP-complete decision problem (Henning and Hedetniemi 2003), i.e., given a positive integer k and a graph G, the problem of deciding if G has a weak Roman dominating set D of cardinality \(|D|\le k\) is NP-complete. Hence, the optimization problem of computing the weak Roman domination number of a graph is NP-hard.
Corollary 3
The problem of computing the secure Italian domination number of a graph is NP-hard.
Proof
By Theorem 2, for any graph G of order n we have that \(\gamma _{_I}^s(G\circ K_2)=n+\gamma _r(G)\). Hence, the problem of computing \(\gamma _r(G)\) is equivalent to the problem of finding \(\gamma _{_I}^s(G\circ K_2)\), which implies that the general problem of computing the secure Italian domination number of a graph is NP-hard. \(\square \)
According to Corollary 3, it would be desirable to obtain tight bound or closed formulas for the secure Italian domination number of a graph. This is precisely the aim of the next sections.
3 General bounds and extremal cases
To begin this section, we proceed to characterize the graphs achieving the following trivial bounds.
Remark 4
For any graph G of order \(n\ge 2\),
$$\begin{aligned} 2 \le \gamma _I^s(G) \le n. \end{aligned}$$
Obviously, when characterizing the graphs achieving the bounds we can restrict ourselves to the case of connected non-trivial graphs, and from that characterization it is easy to deduce the result for non-connected graphs.
Theorem 5
Let G be a connected non-trivial graph of order n. Then the following statements hold.
(i)
\(\gamma _I^s(G) =2\) if and only if \(G \cong K_{n};\)
(ii)
\(\gamma _I^s(G) =n\) if and only if \(G \cong K_{1,n-1}.\)
Proof
If \(G \cong K_{n},\) then obviously \(\gamma _I^s(G) =2.\) Suppose \(\gamma _I^s(G) =2\) and \(G \not \cong K_{n}.\) Let f be a \(\gamma _I^s(G)\)-function and u, v two non-adjacent vertices. If \(f(u)=2\), then \(f(N_G[v])=0\), which is a contradiction. Assume that \(f(u)=0.\) Hence, either u is adjacent to two vertices x, y where \(f(x)=f(y)=1\) or u is adjacent to a vertex z such that \(f(z)=2.\) Thus, since \(\gamma _I^s(G) =2,\) in both cases \(f(v)=0\). In the first case, neither \(f_{x\rightarrow u}\) nor \(f_{y\rightarrow u}\) is an IDF on G, which is a contradiction. In the second case, \(f_{z\rightarrow u}\) is not an IDF on G, which is a contradiction again. Now, if \(f(u)=f(v)=1\), then for any vertex \(x \in V(G){\setminus } \{u,v\}= N_G(u) \cap N_G(v)\) we have that \(f(x)=0\) and neither \(f_{u\rightarrow x}\) nor \(f_{v\rightarrow x}\) is an IDF on G, which is a contradiction again. Therefore, (i) follows.
If \(G \cong K_{1,n-1},\) then it is easy to observe that \(\gamma _I^s(G) =n.\) Conversely, suppose \(\gamma _I^s(G) =n\) and there are two vertices, u, v such that \({\text {d}}_G(u)\ge 2\) and \({\text {d}}_G(v) \ge 2;\) let us choose u, v such that \(uv \in E(G).\) We can define an SIDF g on G such that \(g(u)=0\) and \(g(x)=1\) for any \(x \in V(G) {\setminus } \{u\}\). Notice that \(\omega (g)=n-1<n=\gamma _I^s(G),\) which is a contradiction. Therefore, (ii) follows. \(\square \)
For any vertex \(x\in V(G)\) and any \(\gamma _I^s(G)\)-function \(f(V_0, V_1, V_2)\) such that \(f(x)=2\), we define the following set associated with x and f,
The subgraph of G induced by a set \(S\subseteq V(G)\) will be denoted by \(\langle S \rangle \). From the definition of SIDF on G we have the following straightforward observation.
Observation 6
If there exists a vertex \(x\in V(G)\) and a \(\gamma _I^s(G)\)-function f such that \(f(x)=2\) and \(P_f(x) \ne \emptyset ,\) then \(\langle P_f(x) \rangle \) is a clique.
The k-domination number of a graph G, denoted by \(\gamma _k(G)\), is the cardinality of a smallest set of vertices such that every vertex not in the set is adjacent to at least k vertices in the set. Such sets are called k-dominating sets. Since every 2-dominating set S is a secure dominating set, and the function \(f(V_0,V_1=S,V_2=\emptyset )\) is an IDF, we conclude that
From the inequality \(\gamma _2(G)\ge \gamma _{s}(G)\) and the lower bound stated by the next theorem, we will be able to deduce that the expected inequality \(\gamma _I^s(G)\ge \gamma _{s}(G)\) holds for any graph G.
Let D be a \(\gamma (G)\)-set and \(D'\) a \(\gamma _s(G)\)-set. Let us construct a function f from D and \(D'\) such that
$$\begin{aligned} f(x) = \left\{ \begin{array}{ll} 2&{}\quad \text { if } x \in D \cap D',\\ 1&{}\quad \text { if } x \in (D \cup D') {\setminus } (D \cap D'),\\ 0&{}\quad \text { otherwise.} \end{array} \right. \end{aligned}$$
We claim that f is an SIDF on G. Obviously, f is an IDF on G. For every vertex \(x \in V(G) {\setminus } (D \cup D')\) there exists \(y \in D'\) such that x is protected by y under \(D'.\) We will show that \(f_{y \rightarrow x}\) is an IDF on G. Let \(x'\) be a vertex such that \(f_{y \rightarrow x}(x')=0.\) If \(x' \notin N_G(y),\) then we are done as f is an IDF on G. Assume \(x' \in N_G[y].\) We consider two cases.
Case 1\(x' \in N_G(x).\) If \(y \in D \cap D',\) then \(f_{y \rightarrow x}(x)= f_{y \rightarrow x}(y)=1\). Otherwise there exists \(z \in N_G(x') \cap D\) such that \(f_{y \rightarrow x}(x)= f_{y \rightarrow x}(z)=1\).
Case 2\(x' \notin N_G(x).\) In this case, there exists \(y' \in (D' {\setminus } \{y\}) \cap N_G(x')\) and \(z \in N_G(x') \cap D.\) If \(y'=z,\) then \(f_{y \rightarrow x}(y')=2,\) otherwise \(f_{y \rightarrow x}(y') \ge 1\) and \(f_{y \rightarrow x}(z)\ge 1.\)
According to the two cases above we can conclude that \(f_{y \rightarrow x}\) is an IDF on G. Therefore, f is an SIDF, and so \(\gamma _I^s(G)\le \omega (f)=|D|+|D'|=\gamma (G)+\gamma _s(G)\).
Now we prove the lower bound \(\gamma _I^s(G) \ge \gamma _2(G)\). Let \(g(V_0, V_1, V_2)\) be a \(\gamma _I^s(G)\)-function. Notice that if \(V_2=\emptyset \), then \(V_1\) is a 2-dominating set and so \(\gamma _2(G) \le |V_1|=\gamma _I^s(G)\). Assume that \(V_2\ne \emptyset \). Let \(x \in V_2\) and notice that if \(P_g(x) \ne \emptyset ,\) then the subgraph induced by \(P_g(x)\) is a clique. With this fact in mind, for every \(x \in V_2\) such that \(P_g(x) \ne \emptyset \) we fix one vertex \(x' \in P_g(x),\) and let \(V_g\) be the set of these representatives. Now, if \(u \in V_0\) and u does not belong to any \(P_g(x),\) then \(|N_G(u) \cap (V_1 \cup V_2)|\ge 2,\) while if \(u \in P_g(x)\) for some \(x \in V_2,\) then \(x, x' \in N_G[u].\) Thus \(S=V_1 \cup V_2 \cup V_g\) is a 2-dominating set of G. Therefore, \(\gamma _2(G) \le |S|=|V_1|+ |V_2|+ |V_g| \le |V_1| + 2 |V_2| =\gamma _I^s(G)\) and the lower bound \(\gamma _I^s(G) \ge \gamma _2(G)\) follows.
Finally, we proceed to prove the lower bound \(\gamma _I^s(G) \ge \gamma _r(G)+1\). In this case, let \(h(W_0, W_1, W_2)\) be a \(\gamma _I^s(G)\)-function. If \(\gamma _I^s(G)=|V(G)|\), then we are done, as \(\gamma _r(G)\le |V(G)|-1\) for every non-empty graph. Hence, we fix \(x\in W_0\) and \(y\in W_1\cup W_2\) such that y is a moving neighbour of x. We now construct a weak Roman dominating function \( h'(W'_0, W'_1, W'_2)\), which is defined in two different ways depending on whether \(y\in W_2\) or not.
Case 1\('\)\(y\in W_2\). In this case, we define the function \(h'\) by \(h'(y)=1\) and \(h'(z)=h(z)\) for every \(z\in V(G){\setminus } \{y\}\). Since h is an IDF, G does not have undefended vertices under \(h'\), i.e., \(W_1\cup W_2=W'_1\cup W'_2\) is a dominating set. Moreover, since for every \(v\in W_0=W'_0\), there exits \(u\in W_1\cup W_2\) such that \(h_{u\rightarrow v}\) is an IDF, we conclude that G does not have undefended vertices under \(h'_{u\rightarrow v}\). Therefore, \(h'\) is a weak Roman dominating function on G.
Case 2\('\)\(y\in W_1\). In this case, we define the function \(h'\) by \(W'_0=W_0\cup \{y\}\), \(W'_1=W_1{\setminus } \{y\}\) and \(W'_2=W_2\). Since h and \(h_{y\rightarrow x}\) are IDFs, we can conclude that G does not have undefended vertices under \(h'\). Moreover, for every \(v\in W_0\), there exits \(u\in W_1 \cup W_2\) such that \(h_{u\rightarrow v}\) is an IDF. Hence, if \(u\ne y\), then G does not have undefended vertices under \(h'_{u\rightarrow v}\). Suppose that y is the only moving neighbour of \(v\in W_0\) under h and there exists \(w\in W_0'\) which is undefended under the function \(h'_{x'\rightarrow v}\), where \(x'\in N_G(v)\cap (W_1\cup W_2){\setminus } \{y\}\). In such a case, \(h'(x')=h(x')=1\), \(w\notin N_G(v)\) and \(N_G(w)\cap (W_1\cup W_2)=\{x',y\}\). Thus, \(h_{y\rightarrow v}(N_G(w))=h(x')= 1\), which is a contradiction. Finally, it is readily seen that the set \(X=N_G(y)\cap (W_1\cup W_2)\) is not empty and G does not have undefended vertices under the function \(h'_{z\rightarrow y}\) for every \(z\in X\). Therefore, \(h'\) is a weak Roman dominating function on G.
According to the two cases above, \(\gamma _I^s(G)=\omega (h)=\omega (h')+1\ge \gamma _r(G)+1\). Therefore, the proof is complete. \(\square \)
Next we show that the bounds above are tight.
If G is the graph shown in Fig. 2 or the graph shown in Fig. 1 on the right, then \(\gamma _I^s(G) = \gamma _r(G)+1\).
If \(G \cong K_{1,n-1}\), \(G \cong K_n\) or G is the graph shown in Fig. 1 on the left, then \(\gamma _I^s(G) = \gamma (G) + \gamma _s(G)\).
If G is a corona graph \(H \odot K_p\) for \(p \ge 2\), then \(\gamma _s(G) = \gamma (G) = |V(H)|\) and \(\gamma _2(G)=2 |V(H)|\), which implies that \(\gamma _2(G)=\gamma _I^s(G)= \gamma _s(G)+ \gamma (G)\).
In summary, we can state the following domination chains.
We claim that if \(\gamma _I^s(G)=\gamma _2(G)\), then there exists a \(\gamma _2(G)\)-set S such that for every \(x,y\in S\) either \(S_{xy}=\emptyset \) or \(\langle S_{xy} \rangle \) is a clique.
Let \(g(V_0, V_1, V_2)\) be a \(\gamma _I^s(G)\)-function and S the 2-dominating set constructed in the proof of Theorem 7, i.e., if \(V_2=\emptyset \), then \(S=V_1\), while if \(V_2\ne \emptyset \), then \(S=V_1\cup V_2\cup V_g\). Since \(\gamma _I^s(G)=\gamma _2(G)\), we have that S is a \(\gamma _2(G)\)-set. Suppose to the contrary that there exist two different vertices \(x,y\in S\) and two different non-adjacent vertices \(u,v\in V_0\) such that \(u,v\in S_{x,y}\). We differentiate the following cases.
Case 1\(x,y\in V_1\). Since u and v are not adjacent, neither \(g_{x \rightarrow u}\) nor \(g_{y \rightarrow u}\) is an IDF, which is a contradiction, as g is a \(\gamma _I^s(G)\)-function.
Case 2\(x\in V_1\) and \(y\in V_2\). Since \(\langle S_{xy} \rangle \) is not a clique and g is a \(\gamma _I^s(G)\)-function, \(P_g(y)=\emptyset \). Hence, \(|V_g|<|V_2|\), which implies that \(\gamma _2(G) = |S|=|V_1|+ |V_2|+ |V_g| <|V_1| + 2 |V_2| =\gamma _I^s(G)\), and this is a contradiction.
Case 3\(x,y\in V_2\). Since \(S_{xy}\ne \emptyset \) and g is a \(\gamma _I^s(G)\)-function, \(P_g(x)=\emptyset \) or \(P_g(y)=\emptyset \). Hence, \(|V_g|<|V_2|\) and, as in Case 2, we arrive to a contradiction.
Case 4\(x\in V_g\). If \(x\in P_g(y)\), then \(S_{xy}\subseteq P_g(y)\) and \(\langle P_g(y) \rangle \) is a clique, which is a contradiction. Now, if \(y\in V_g{\setminus } \{x\}\), then \(S_{xy}=\emptyset \), which is a contradiction. Finally, if \(y\in V_1\cup V_2\) and \(x\not \in P_g(y)\), then \(u,v\in P_g(y)\), which is a contradiction, as \(\langle P_g(y) \rangle \) is a clique.
According to the four cases above, the proof of our claim is complete. Therefore, if for every \(\gamma _2(G)\)-set S there exist two vertices \(x,y\in S\) such that the set \(S_{xy}\) contains two non-adjacent vertices, then \(\gamma _I^s(G)\ne \gamma _2(G)\), and by Theorem 7 we conclude that \(\gamma _I^s(G)\ge \gamma _2(G)+1.\)\(\square \)
The bound above is tight. To see this we can take, for instance, the graph shown in Fig. 1, on the right. Now, in order to show that the converse of Theorem 9 does not hold, we can consider the graph shown in Fig. 1, on the left, where \( \gamma _I^s(G)=5=\gamma _2(G)+1\) and the \(\gamma _2(G)\)-set S consisting of all vertices of degree five satisfies that \(\langle S_{xy} \rangle \) is a clique for every \(x,y\in S\). Another example in the same direction is the graph sown in Fig. 2, where \( \gamma _I^s(G)=7=\gamma _2(G)+1\) and the \(\gamma _2(G)\)-set S consisting of all black-coloured vertices, except the central one, satisfies \(S_{xy}=\emptyset \) for every \(x,y\in S\).
4 The particular case of cycles and trees
Next we obtain closed formulas for the secure Italian domination number of cycles and paths. For this purpose, we shall need the following lemma.
Lemma 10
If \(G\cong P_n\) or \(G\cong C_n,\) then there exists a \(\gamma _I^s(G)\)-function \(f(V_0, V_1, V_2)\) such that \(V_2 = \emptyset .\)
Proof
It readily seen that the result follows for \(n\le 5\). Assume that \(n\ge 6\). Let \(f(V_0, V_1, V_2)\) be a \(\gamma _I^s(G)\)-function such that \(|V_2|\) is minimum among the functions satisfying Lemma 1. Suppose that there exists \(x\in V(G)\) such that \(f(x)=2\). As assumed, x is not a leaf. Let \(N_G(x)=\{y,z\}\). If \(f(y)\ge 1\), then we can construct a \(\gamma _I^s(G)\)-function \(g(W_0, W_1, W_2)\) where \(g(x)=1\), \(g(z)=\max \{1,f(z)\}\) and \(g(v)=f(v)\) for every \(v\in V(G){\setminus } \{x,z\}\), which is a contradiction, as \(|W_2|<|V_2|\). Hence, \(f(y)=f(z)=0.\) Let \(\{y'\}=N(y){\setminus } \{x\}\) and \(\{z'\}=N(z){\setminus } \{x\}\). Notice that \(f(y')\ge 1\) or \( f(z')\ge 1\), otherwise f is not a \(\gamma _I^s(G)\)-function. Now, if \(f(y')\ge 1\), then x is a moving neighbour of z, and so we can construct a \(\gamma _I^s(G)\)-function \(g(W_0, W_1, W_2)\) where \(g(x)=g(z)=1\) and \(g(v)=f(v)\) for every \(v\in V(G){\setminus } \{x,z\}\), which again is a contradiction, as \(|W_2|<|V_2|\). \(\square \)
The cases \(n\in \{3,4\}\) are easy to check. Hence, from now on we assume that \(n\ge 5\). Let \(V(C_n)=\{v_0, v_1,\dots , v_{n-1}\}\), where consecutive vertices are adjacent. First we show that \(\gamma _I^s(C_n) \le \lceil \frac{3n}{5} \rceil \) by constructing a secure Italian dominating function \(f(V_0,V_1, \emptyset )\) of weight \(\omega (f)=\lceil \frac{3n}{5} \rceil \). For \(n \equiv i \pmod 5\) we define \(l=\frac{n-i}{5}\) and consider a partition \(\Pi _l\) of \(V(C_n)\) defined as follows. If \(i=0\), then \(\Pi _l=\{X_0,\dots , X_{l-1}\}\) and if \(i\ge 1\), then \(\Pi _l=\{X_0,\dots , X_{l-1},X_l\}\). For any \(j<l\), the set \(X_j=\{v_{5j},v_{5j+1}, \ldots , v_{5j+4}\}\) contains five consecutive vertices of \(C_n\), while \(X_l\) contains the remaining i consecutive vertices.
For every \(0 \le j \le l-1,\) let \(f(v_{5j})=1,\)\(f(v_{5j+1})=0,\)\(f(v_{5j+2})=1,\)\(f(v_{5j+3})=1,\)\(f(v_{5i+4})=0.\) We can see these weights as l consecutive sequences of numbers 10110. The weight of the vertices in \(X_l\) is assigned as follows.
If \(n \equiv 1 \pmod 5\), then \(f(v_{n-1})=1\).
If \(n \equiv 2 \pmod 5\), then \(f(v_{n-2})=f(v_{n-1})=1\).
If \(n \equiv 3 \pmod 5\), then \(f(v_{n-2})=0\) and \(f(v_{n-3})=f(v_{n-1})=1\).
If \(n \equiv 4 \pmod 5\), then \(f(v_{n-3})=0\) and \(f(v_{n-4})=f(v_{n-2})=f(v_{n-1})=1\).
The weight of f can be expressed in terms of \(n \equiv i \pmod 5\) as follows.
If \(i=0\), then \(\omega (f)=\frac{3n}{5} = \lceil \frac{3n}{5}\rceil .\)
If \(i=1\) or \(i=2\), the \(\omega (f)=\frac{3(n-i)}{5} +i = \lceil \frac{3n}{5}\rceil .\)
If \(i=3\) or \(i=4\), the \(\omega (f)=\frac{3(n-i)}{5} +i-1 = \lceil \frac{3n}{5}\rceil .\)
Notice that if \(f(x)=0\) for \(x\in V(C_n)\), then x belongs to a sequence of consecutive vertices axbc with sequence of weights 1011, or belongs to a sequence of consecutive vertices abxc with sequence of weights 1101. In both cases, \(f_{b\rightarrow x}\) is an IDF. Hence, f is an SIDF and so \(\gamma _I^s(C_n)\le \omega (f)= \lceil \frac{3n}{5}\rceil .\)
Now we show that \(\gamma _I^s(C_n) \ge \lceil \frac{3n}{5} \rceil .\) Let \(f(V_0, V_1, V_2)\) be a \(\gamma _I^s(C_n)\)-function which satisfies Lemma 10. Since \(V_2 = \emptyset \), we have that \(V_1\) is a 2-dominating set, and so for any vertex \(v_i \in V_0,\) we have that \(f(v_{i-1})=f(v_{i+1})=1\). Moreover, if \(v_{i-1}\) is the moving neighbour of \(v_i\), then \(f(v_{i-2})=1\), otherwise the moving neighbour of \(v_i\) is \(v_{i+1}\) and so \(f(v_{i+2})=1\). Thus, for every sequence of five consecutive vertices, at most two of them can belong to \(V_0\), i.e.,
$$\begin{aligned} \psi _i=f(v_{i-2})+f(v_{i-1})+f(v_{i})+f(v_{i+1})+f(v_{i+2})\ge 3 \text { for every } i\in \{0,\dots , n\}. \end{aligned}$$
Let G be a graph and \(e \in E(G)\). The edge-deletion subgraph \(G-e\) of G is defined to be \(G-e= (V(G), E(G) {\setminus } \{e\}).\) Observe that every \(\gamma _I^s(G-e)\)-function is an SIDF on G, which implies the following result.
The cases where \(n\le 4\) are easy to check. Hence, from now on we assume that \(n\ge 5\). Let \(f(V_0, V_1, V_2)\) be a \(\gamma _I^s(P_n)\)-function which satisfies Lemma 10. In this proof we adapt the procedure developed in the proof of Proposition 11 to the case of paths. Thus, we assume that \(V(P_n)=\{v_0, v_1,\dots , v_{n-1}\}\), where consecutive vertices are adjacent. From Eq. (1) we know that \(\psi _i\ge 3 \text { for every } i\in \{0,\dots , n\}.\) In this case, the weight of the leaves has to be one, i.e., \(f(v_0)=f(v_{n-1})=1\). Hence, the sequence \(f(v_0)f(v_1)f(v_2)f(v_3)\) has to be 1011 or 1101. Analogously, the sequence \(f(v_{n-4})f(v_{n-3})f(v_{n-2})f(v_{n-1})\) has to be 1101 or 1011. In all cases, \(\psi _1=f(v_{3})+f(v_{2})+f(v_{1})+f(v_{0})+f(v_{n-1})\ge 4\) and \(\psi _{n-2}=f(v_{0})+f(v_{n-1})+f(v_{n-2})+f(v_{n-3})+f(v_{n-4})\ge 4\). Hence,
which implies that \(\gamma _I^s(P_n)\ge \lceil \frac{3n+2}{5}\rceil .\)
To conclude the proof we only need to construct an SIDF as described in the proof of Proposition 11, with the only difference that, for \(n \equiv 0\pmod 5\) we take \(f(v_{n-1})=1\) and for \(n \equiv 3\pmod 5\) we take \(f(v_{n-2})=1.\) In this case, the weight of f can be expressed as follows.
If \(n \equiv 0 \pmod 5\), then \(\omega (f)=\frac{3n}{5} +1= \lceil \frac{3n+2}{5}\rceil .\)
If \(n \equiv 1 \pmod 5\), the \(\omega (f)=\frac{3(n-1)}{5} +1 = \lceil \frac{3n+2}{5}\rceil .\)
If \(n \equiv 2 \pmod 5\), the \(\omega (f)=\frac{3(n-2)}{5} +2 = \lceil \frac{3n+2}{5}\rceil .\)
If \(n \equiv 3 \pmod 5\), the \(\omega (f)=\frac{3(n-3)}{5} +3 = \lceil \frac{3n+2}{5}\rceil .\)
If \(n \equiv 4 \pmod 5\), the \(\omega (f)=\frac{3(n-4)}{5} +3 = \lceil \frac{3n+2}{5}\rceil .\)
From Remark 8 (c) we learned that \(\gamma _I^s(G)\ge \gamma (G)+1\) for every non-empty graph G. We proceed to characterize the trees T satisfying the equalities \(\gamma _I^s(T)=\gamma (T)+1\) or \(\gamma _I^s(T)=\gamma (T)+2\). We begin with the following observation.
Observation 15
If T is a tree of order \(n\ge 3\), then always is possible to choose a \(\gamma (T)\)-set not containing any leaf of T.
From Observation 15 and Lemma 1 we have the following lemma.
Lemma 16
Let T be a tree. If \(\gamma _I^s(T)=\gamma (T)+1,\) there there exists at most one strong support s in T and s is the neighbour of exactly two leaves.
We are now ready to prove the following characterization.
Theorem 17
\(\gamma _I^s(T)=\gamma (T)+1\) if and only if \(T \cong P_2\) or \(T \cong P_4.\)
Proof
If \(T \cong P_2\) or \(T \cong P_4\), then obviously \(\gamma _I^s(T)=\gamma (T)+1\).
Let n be the order of T. If \(n\le 4\), then the only trees with \(\gamma _I^s(T)=\gamma (T)+1\) are \(P_2\) and \(P_4\), as desired. From now on, suppose that T is a tree of minimum order \(n\ge 5\) among the trees satisfying the equality \(\gamma _I^s(T)=\gamma (T)+1\). Obviously, if \(T'\) is a tree of order less than n such that \(\gamma _I^s(T')=\gamma (T')+1,\) then \(T'\) is either \(P_2\) or \(P_4.\) Let f be a \(\gamma _I^s(T)\)-function satisfying Lemma 1. Let \(P=(v_0, \ldots , v_l)\) be a longest path in T. If \(l\le 2\), then \(T\cong K_{1,n-1}\), which is contradiction with Lemma 16. Thus, \(l\ge 3\). Assume first that \({\text {d}}_T(v_1)>2.\) Then, from Lemma 16, \({\text {d}}_T(v_1)=3\), and so there exist two leaves \(x,v_0\) adjacent to \(v_1.\) Let \(T_1 = T- \{v_0, x, v_1\}.\) Since \(f(v_0)=f(x)=1\) and \(f(v_1)+f(v_2)\ge 1\), we deduce that \(\gamma _I^s(T_1)+2 \le \gamma _I^s(T)=\gamma (T)+1\le \gamma (T_1)+1+1,\) what gives \(\gamma _I^s(T_1)\le \gamma (T_1),\) which is a contradiction with Remark 8 (c). Hence, \({\text {d}}_T(v_1)= 2.\) Now, let \(T_2 = T- \{v_0, v_1\}.\) Since \(f(v_0)=1\) and \(f(v_1)+f(v_2)\ge 1\), we deduce that \(\gamma _I^s(T_2)+1 \le \gamma _I^s(T)=\gamma (T)+1\le \gamma (T_2)+1+1,\) what gives \(\gamma _I^s(T_2)\le \gamma (T_2)+1.\) Thus, Remark 8 (c) leads to \(\gamma _I^s(T_2)=\gamma (T_2)+1\), and by assumption \(T_2\cong P_2\) or \(T_2\cong P_4\). If \(T_2\cong P_2\), then \(T\cong P_4\), which is a contradiction, as \(n\ge 5\). If \(T_2\cong P_4\), then \(T\cong P_6\) or \(T\cong P_3\odot K_1\), but in both cases \(\gamma _I^s(T)>\gamma (T)+1,\) which is a contradiction again. \(\square \)
From the result above we conclude that if \(T \not \cong P_2\) and \(T \not \cong P_4,\) then \(\gamma _I^s(T) \ge \gamma (T)+2.\) Below we give the full characterization of the extremal trees. First we define a family \(\mathcal {R}\) of trees. A spider is a graph obtained from the star \(K_{1,t}\) for \(t \ge 1\) by subdividing each edge of the star exactly once. Obviously, if T is a spider with \(t=1\), then \(T\cong P_3\). If \(t \ge 3\) and we subdivide once exactly \(t-1\) of the edges of a star \(K_{1,t}\), then we obtain a tree called slightly wounded spider. We say that \(T\in \mathcal {R}\) if T is a spider, a slightly wounded spider with \(t\ge 3\), a path \(P_6,\) a path \(P_7\), a corona \(P_4 \odot K_1\), a star \(K_{1,3}\) with one subdivided edge (we denote it by \(T_{*}\)) or a star \(K_{1,3}\) with one edge subdivided once and one edge subdivided twice (for simplicity we denote it by \(T_{**}\)).
Theorem 18
Let T be a tree. Then \(\gamma _I^s(T) = \gamma (T) +2\) if and only if \(T\in \mathcal {R}\).
Proof
If \(T\in \mathcal {R}\), then obviously \(\gamma _I^s(T)=\gamma (T)+2\). To prove the converse, we use induction on n, the number of vertices of a tree. The smallest tree such that \(\gamma _I^s(T)=\gamma (T)+2\) is \(T\cong P_3\), which is a spider, so \(T\in \mathcal {R}\). Assume that \(n\ge 4\) and if \(T'\) is a tree with \(|V(T')|<n\) and \(\gamma _I^s(T')=\gamma (T')+2,\) then \(T'\in \mathcal {R}.\)
Let T be a tree of order \(n \ge 4\) such that \(\gamma _I^s(T)=\gamma (T)+2\), and let f be a \(\gamma _I^s(T)\)-function which satisfies Lemma 1 and the values of f on supports on the longest paths is as small as possible. Notice that \(f(x)=0\) for every support x of degree two. Let \(P=(v_0, \ldots , v_l)\) be a longest path in T. We differentiate some cases according to the degree of \(v_1\) and \(v_2\).
Case 1\({\text {d}}_T(v_1)>2\). Let \(T'=T-\{v_0\}\). Since \(v_1\) is a support of \(T'\), the restriction of f to \(T'\) is an SIDF. Thus, \(\gamma _I^s(T')\le \gamma _I^s(T)-1\) and \(\gamma (T')=\gamma (T)\). From our assumption, \(\gamma _I^s(T)=\gamma (T)+2\), which implies that \(\gamma _I^s(T')=\gamma (T')+1\). By Theorem 17, \(T'\cong P_2\) or \(T'\cong P_4\). And since \({\text {d}}_T(v_1)>2\), the only possibility is \(T'\cong P_4\), where \(v_1\) is a support of \(P_4\). This implies that \(T\cong T_*\in \mathcal {R}\).
Case 2\({\text {d}}_T(v_1)=2\). Let \(T'=T-\{v_0,v_1\}\). From the choice of f we have \(f(v_0)=1\) and \(f(v_1)=0.\) Thus, the restriction of f to \(T'\) is an SIDF, which implies that \(\gamma _I^s(T')\le \gamma _I^s(T)-1=\gamma (T)+1\). Moreover, \(\gamma (T')+1\le \gamma _I^s(T')\), by Remark 8. Hence,
With this facts in mind, we consider the following three subcases, depending on the degree of vertex \(v_2.\)
Subcase 2.1\({\text {d}}_T(v_2)>2\) and there exists a vertex \(s\in N_T(v_2){\setminus }\{v_1,v_3\}\) which is a support. Since \(s\in N_T(v_2)\) is a support, \(\gamma (T')=\gamma (T)-1\). Hence, by Eq. (2) we have that \(\gamma (T')+1\le \gamma _I^s(T')\le \gamma (T)+1=\gamma (T')+2\), and so either \(\gamma _I^s(T')= \gamma (T')+1\) or \(\gamma _I^s(T')= \gamma (T')+2\). Observe that since there exists a vertex \(s\in N_T (v_2){\setminus } \{v_1, v_3\}\) which is a support vertex, it follows that \(|V (T')|\ge 5\) (because of the diametral path P). Using this fact, we deduce that \(\gamma _I^s(T')= \gamma (T')+1\) cannot occur. So, if \(\gamma _I^s(T')= \gamma (T')+2\), then by induction hypothesis we have that \(T'\in \mathcal {R}\). If \(T'\) is a spider or a slightly wounded spider, then T is also a spider or a slightly wounded spider, respectively, so \(T\in \mathcal {R}\). Since \(s\not \in \{v_1,v_3\}\), \(T'\not \cong T_*\) and, in the remaining cases it is easy to check that \(\gamma _I^s(T)\ge \gamma (T)+3\), which is a contradiction.
Subcase 2.2\({\text {d}}_T(v_2)>2\) and every vertex in \(N_T(v_2){\setminus }\{v_1,v_3\}\) is a leaf. Since \(v_2\) is a support in \(T'\), \(\gamma (T')=\gamma (T)-1\). Thus, as in Subcase 2.1, either \(\gamma _I^s(T')=\gamma (T')+1\) or \(\gamma _I^s(T')=\gamma (T')+2.\) If \(\gamma _I^s(T')=\gamma (T')+1\), then from Theorem 17 and from the fact that \({\text {d}}_{T'}(v_2)\ge 2\), we deduce that \(T'=P_4\) and T is a slightly wounded spider, so \(T\in \mathcal {R}\). Now, if \(\gamma _I^s(T')=\gamma (T')+2\), then by induction hypothesis, \(T'\in \mathcal {R}\). If \(T'\) is a spider with \(t=1\), then \(T=T_*\in \mathcal {R}\). If \(T'\) is a slightly wounded spider with \(t=3\), then \(T=P_4\odot K_1 \in \mathcal {R}\). In the remaining cases it is easy to check that \(\gamma _I^s(T)\ge \gamma (T)+3\), which is a contradiction.
Subcase 2.3\({\text {d}}_T(v_2)=2.\) Obviously, \(\gamma (T')\ge \gamma (T)-1\). Thus, by Eq. (2), \(\gamma (T')+1\le \gamma _I^s(T')\le \gamma (T')+2\). By Theorem 17, if \(\gamma _I^s(T')= \gamma (T')+1\), then \(T'\cong P_2\) or \(T'\cong P_4\). In the first case, \(T\cong P_4\), which is a contradiction, as \(\gamma _I^s(P_4)=3\ne \gamma (P_4)+2\). In the second case \(T\cong P_6\in \mathcal {R}\). Now, if \(\gamma _I^s(T')= \gamma (T')+2\), then by induction hypothesis, \(T'\in \mathcal {R}\). If \(T'\) is a spider with \(t=2\), then \(T\cong P_7\in \mathcal {R}\). If \(T'\cong T_*\) and \(v_2\) is a leaf of \(T'\) adjacent to a central vertex, then \(T\cong T_{**}\in \mathcal {R}\). In the remaining cases it is easy to check that \(\gamma _I^s(T)\ge \gamma (T)+3\), which is a contradiction. \(\square \)
5 The particular case of join graphs
To begin this section we consider the class of join graphs of the form \(K_n+G\).
Theorem 19
For any non-complete graph G and any integer \(n\ge 2\), the following statements hold.
Since G is a non-complete graph, \(K_1+G\) is a non-complete graph, and so Theorem 5 leads to \(\gamma _I^s(K_1+G) \ge 3\).
Now, let S be a \(\gamma (G)\)-set. It is immediate that the function \(f(V_0,V_1,V_2)\), defined on \(K_1+G\) by \(V_2=V(K_1)\) and \(V_1=S\), is an SIDF, which implies that \(\gamma _I^s(K_1+G) \le \omega (f)= \gamma (G)+2.\) To conclude the proof of (i) we take a \(\gamma _r(G)\)-function \(g(X_0,X_1,X_2)\) and define a function \(h(Y_0,Y_1,Y_2)\) on \(K_1+G\) by \(Y_1=X_1\cup V(K_1)\) and \(V_2=X_2.\) Obviously, h is an SIDF and so \(\gamma _I^s(K_1+G) \le \omega (h)=\gamma _r(G)+1\).
Finally, if \(n\ge 2\), then \(K_n+G=K_1+(K_{n-1}+G)\). Since \(\gamma (K_1+G)=1\), from (i) we deduce (ii). \(\square \)
From the result above we deduce the following corollary.
Corollary 20
If \(\gamma _r(G)=2\), then \(\gamma _I^s(K_1+G)=3\).
Next we consider the class of join graphs \(G+H\) where neither G nor H is a complete graph.
The lower bound is a consequence of Theorem 5, as \(G+H\) is a non-complete graph. Now, since G and H are non-trivial graphs, we can construct a function \(f(V_0,V_1,V_2)\) on \(G+H\) by taking two vertices \(u,v\in V(G)\) and two vertices \(x,y\in V(H)\), and defining \(V_2=\{u,x\}\) and \(V_1=\{v,y\}\). It is readily seeing that f is an SIDF, and so \(\gamma _I^s(G+H) \le \omega (f)=6\). To conclude the proof we only need to observe that \(\gamma _I^s(G)\ge 3\) and so, from any \(\gamma _I^s(G)\)-function \(g(X_0,X_1,X_2)\), we can construct an SIDF \(g'(Y_0,Y_1,Y_2)\) on \(G+H\) by \(Y_0=X_0\cup V(H)\), \(Y_1=X_1\) and \(Y_2=X_2\). Therefore, \(\gamma _I^s(G+H) \le \omega (g')=\gamma _I^s(G).\)\(\square \)
Now we consider some particular cases.
Theorem 22
The following statements hold.
(a)
If \(\gamma _I^s(G)=3,\) then \(\gamma _I^s(G+H)=3\) for every graph H.
(b)
If \(\gamma (G)=\gamma (H)=2,\) then \(3 \le \gamma _I^s(G + H) \le 4.\)
(c)
If \(\gamma _r(G)=2\) and \(\gamma _r(H)=2,\) then \(\gamma _I^s(G+H)=3.\)
(d)
If \(\gamma _r(G)\ge 3\) and H is a non-complete graph, then \(3\le \gamma _I^s(G+H)\le \min \{6, \gamma _r(G)+1\}.\)
Proof
If H is a non-complete graph, then we deduce (a) from Theorem 21. Now, if \(H\cong K_n\), \(n\ge 2\) then we apply Theorem 19 (ii), while for \(H\cong K_1\) we apply Theorems 7 and 19 (i).
In the case of item (b), we only need to observe that for any \(\gamma (G)\)-set S and any \(\gamma (H)\)-set \(S'\) we can define an SIDF \(f(V_0,V_1,V_2)\) on \(G+H\), as \(V_1=S\cup S'\) and \(V_2=\emptyset \). Thus, \(3\le \gamma _I^s(G+H) \le \omega (f)=4.\)
Now, assume that \(\gamma _r(G)=2\) and \(\gamma _r(H)=2\). Let \(v\in V(H)\) be a vertex of a positive weight under any \(\gamma _r(H)\)-function. Let \(f'(W_0,W_1,W_2)\) be a \(\gamma _r(G)\)-function. We define a function \(f''(U_0,U_1,U_2)\) on \(G+H\) by \(U_1=W_1\cup \{v\}\) and \(U_2=W_2.\) Notice that either v is a universal vertex of H or \(\langle V(H){\setminus } N[v] \rangle \) is a clique. Hence, \(f''\) is an SIDF on \(G+H\). Therefore, \(3\le \gamma _I^s(G+H)\le \omega (f'')=3\), concluding that (c) follows.
To conclude the proof, we take one vertex \(v\in V(H)\), a \(\gamma _r(G)\)-function \(g(X_0,X_1,X_2)\) and define a function \(g'(Y_0,Y_1,Y_2)\) on \(G+H\) by \(Y_1=X_1\cup \{v\}\) and \(V_2=X_2.\) Obviously, if \(\gamma _r(G)\ge 3\), then \(g'\) is an SIDF and so \(\gamma _I^s(G+H) \le \omega (g')=\gamma _r(G)+1\). Therefore, by Theorem 21 we conclude that (d) follows. \(\square \)
Since \(\gamma _r(G)=2\) if and only if G is a non-complete graph with \(\gamma (G)=1\) or \(\gamma _s(G)=2\), from Theorem 22 (c) and Corollary 20 we deduce the following result.
Remark 23
The following statements hold.
(a)
If \(\gamma (G)=\gamma (H)=1\) and (\(H\not \cong K_n\) or \(G \not \cong K_{n'}\)), then \(\gamma _I^s(G+H)=3.\)
(b)
If \(\gamma (G)=1\) and \(\gamma _s(H)=2,\) then \(\gamma _I^s(G+H)=3.\)
(c)
If \(\gamma _s(G)=2\) and \(\gamma _s(H)=2,\) then \(\gamma _I^s(G+H)=3.\)
Next we consider the classes of fan and wheel graphs.
Fig. 3
\(\gamma _I^s(K_1+P_5)=3\) and \(\gamma _I^s(K_1+P_6)=4\)
×
The Italian domination number and weak Roman domination number of a cycle \(C_n\), where \(n\ge 4\), was determined in Chellali et al. (2016) and in Henning and Hedetniemi (2003), respectively.
Lemma 24
For \(n\ge 4\),
1.
(Chellali et al. 2016) \(\gamma _I(C_n)= \left\lceil \frac{n}{2} \right\rceil \),
2.
(Henning and Hedetniemi 2003) \(\gamma _r(C_n)=\left\lceil \frac{3n}{7}\right\rceil \).
Proposition 25
Let \(n\ge 4\) be an integer. For the classes of fan graphs \(K_1+P_n\) and wheel graphs \(K_1+C_n\),
The cases \(n\in \{4,5,6\}\) are easy to check. Hence, from now on we assume that \(n\ge 7\). In Fig. 3 we show examples of \(\gamma _I^s(K_1+P_n)\)-functions for \(n=5\) and \(n=6\).
Let \(P_n=(x_1,\dots ,x_n)\) and let S be a \(\gamma (P_{n-2})\)-set, where \(P_{n-2}\) is obtained from \(P_n\) by removing \(x_{n-1}\) and \(x_n\). We can construct an SIDF g on \(K_1+P_n\) by assigning the label 1 to every vertex in S, label 2 to the vertex of \(K_1\) and 0 to the remaining vertices. Hence, \(\gamma _I^s(K_1+P_n)\le \omega (g)=2+\gamma (P_{n-2})=2+\left\lceil \frac{n-2}{3} \right\rceil .\)
In order to show that \(\gamma _I^s(K_1+C_n)\ge 2+\left\lceil \frac{n-2}{3} \right\rceil \), let f be a \(\gamma _I^s(K_1+C_n)\)-function, \(f'\) the restriction of f to \(C_n\) and \(V(K_1)=\{v\}\). We differentiate three cases.
Case 1\(f(v)=0\). In this case \(f'\) is an SIDF on \(C_n\) and so \(\gamma _I^s(K_1+C_n)=\omega (f)=\omega (f')\ge \gamma _I^s(C_n)\ge \gamma _I(C_n)=\left\lceil \frac{n}{2} \right\rceil \ge 2+\left\lceil \frac{n-2}{3} \right\rceil \) for \(n\ge 7\).
Case 2\(f(v)=1\). If \(f'\) is a WRDF on \(C_n\), then using Lemma 24\(\gamma _I^s(K_1+C_n)=\omega (f)=1+\omega (f')\ge 1+\gamma _r(C_n)=1+\left\lceil \frac{3n}{7}\right\rceil \ge 2+\left\lceil \frac{n-2}{3} \right\rceil \). Now, if \(f'\) is not a WRDF on \(C_n\), then there exists \(u\in V(C_n)\) such that \(f_{v \rightarrow u}\) is an IDF on \(C_n\). Hence, using Lemma 24\(\gamma _I^s(K_1+C_n)=\omega (f)=1+\omega (f')\ge \gamma _I(C_n)= \left\lceil \frac{n}{2} \right\rceil \ge 2+\left\lceil \frac{n-2}{3} \right\rceil \) for \(n\ge 7\).
Case 3\(f(v)=2\). If \(f(N_{C_n}[x])>0\) for every \(x\in V(C_n)\), then \(\gamma _I^s(K_1+C_n)=\omega (f)\ge 2+\gamma (C_n)= 2+\left\lceil \frac{n}{3} \right\rceil > 2+\left\lceil \frac{n-2}{3} \right\rceil .\) Now, if there exists exactly one vertex \(x\in V(C_n)\) such that \(f(N_{C_n}[x])=0\), then \(\gamma _I^s(K_1+C_n)=\omega (f)\ge 2+\gamma (P_{n-1})= 2+\left\lceil \frac{n-1}{3} \right\rceil \ge 2+\left\lceil \frac{n-2}{3} \right\rceil .\) Finally, suppose that there exist two vertices \(x,y\in V(C_n)\) such that \(f(N_{C_n}[x])=f(N_{C_n}[y])=0\). In such a case, x and y have to be adjacent, otherwise neither \(f_{v \rightarrow x}\) nor \(f_{v \rightarrow y}\) is an IDF on \(K_1+C_n\), which is a contradiction. Hence, \(\gamma _I^s(K_1+C_n)=\omega (f)\ge 2+\gamma (P_{n-2})= 2+\left\lceil \frac{n-2}{3} \right\rceil .\)
According to the three cases above we conclude that \(\gamma _I^s(K_1+C_n)\ge 2+\left\lceil \frac{n-2}{3} \right\rceil .\)
Finally, since \(K_1+P_n\) is a spanning subgraph of \(K_1+C_n\), by Theorem 12 we have that \(\gamma _I^s(K_1+C_n)\le \gamma _I^s(K_1+P_n)\). Therefore, the result follows. \(\square \)
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
