A \(\{2\}\)-dominating function (\(\{2 \}\)DF) on a graph \(G=(V(G),E(G))\) is a function \(f : V(G) \rightarrow \{0,1,2 \}\) such that \(f(N[v]) \geq 2\) for every \(v \in V(G)\), where \(N[v]\) is the closed neighourhood of \(v\). The \(\{2\}\)-domination number of \(G\) is the minimum weight \(\omega(f) = \sum\limits_{v \in V(G)} f(v)\) among all \(\{2 \}\)-dominating functions on \(G\). In this article, we prove that if \(G\) and \(H\) are graphs with no isolated vertex, then for any vertex \(v \in V(H)\) there are six closed formulas for the \(\{2\}\)-domination number of the rooted product graph \(G \circ_v H\). We also characterize the graph \(G\) and \(H\) that satisfy each of these formulas.
Let \(G\) be an undirected graph with vertex set \(V(G)\) and edge set \(E(G)\). The order \(|V(G)|\) of \(G\) is denoted by \(n(G)\). The open neighborhood of \(v \in V(G)\) is \(N(v)=\{ w \in V(G) : vw \in E(G)\}\) and its closed neighborhood is \(N[v]=N(v) \cup \{v\}\). When expressing the given graph \(G\), \(N(v)\) is denoted as \(N_G(v)\). The \(\{2\}\)-domination in graphs has been studied in [1, 2, 6, 8, 11]. A \(\{2\}\)-dominating function (\(\{2 \}\)DF) on a graph \(G\) is a function \(f : V(G) \rightarrow \{0,1,2 \}\) such that \(f(N[v]) \geq 2\) for every \(v \in V(G)\). A \(\{2 \}\)DF \(f\) gives an ordered partition \(f(A_0,A_1,A_2)\), where \(A_i:= \{ x \in V(G) : f(x)=i \}\). The \(\{2\}\)-domination number of \(G\), denoted by \(\gamma_{\{2 \}}(G)\), is the minimum weight \(\omega(f) := \sum\limits_{v \in V(G)} f(v)\) among all \(\{2 \}\)-dominating functions on \(G\). A \(\gamma_{\{2 \}}(G)\)-function is a \(\{2 \}\)DF of \(G\) with the weight \(\gamma_{\{2 \}}(G)\).
In [3], Godsil and McKay introduced the concept of rooted product graph. Given a graph \(G\) of order \(n(G)\) and a graph \(H\) with root vertex \(v\), the rooted product graph \(G \circ_v H\) is the graph obtained from \(G\) and \(H\) by taking one copy of \(G\) and \(n(G)\) copies of \(H\) and identifying the \(i\)th vertex of \(G\) with the root vertex \(v\) in the \(i\)th copy of \(H\) for every \(i \in \{1, \dotsc, n\}\). For each \(x \in V(G)\), the copy of \(G \circ_v H\) containing \(x\) is denoted by \(H_x\), and for every function \(f\) on \(G \circ_v H\), the restriction of \(f\) to \(V(H_x)\) and \(V(H_x) \setminus \{ x \}\) is denoted by \(f_x\) and \(f_x^{-}\), respectively.
Various domination parameters on rooted product graphs have been studied in [4, 5, 7, 9, 10, 12]. In this article, we study the \(\{2\}\)-domination number of rooted product graphs following the methodology of [9].
In the rest of this section, we present some definition and basic results. Given a graph \(G\), a leaf of \(G\) is a vertex of degree one. A support vertex is a vertex adjacent to a leaf. We denote the sets of leaves and support vertices by \(\mathcal{L}(H)\) and \(\mathcal{S}(H)\), respectively. For a subset \(S\) of \(V(G)\), \(G -S\) denotes the subgraph of \(G\) induced by \(V(G) \setminus S\).
Theorem 1.1. Let \(G\) be a graph with no isolated vertex. Then \(\gamma(G) +1 \leq \gamma_{\{2\}}(G) \leq 2\gamma(G)\).
Now, we introduce a new domination parameter which is expressed as one of possible values in our main theorem (See Theorem 2.5). An ordered pair \((K, \phi)\) is a quasi \(\{2\}\)-dominating pair of \(G\) if \(K \subseteq V(G)\) and \(\phi\) is a \(\{2\}\)DF of \(G – K\). The quasi \(\{2\}\)-domination number of \(G\) is defined to be \(\gamma_{q\{2\}}(G):= \text{min} \{ | K| + \omega(\phi) : K \subseteq V(G) ~\text{and}~ \phi ~\text{is a}~\){2}\(\text{DF} ~\text{of}~ G – K \}\). A \(\gamma_{q\{2\}}(G)\)-pair is a quasi \(\{2\}\)-dominating pair \((K, \phi)\) which satisfies the condition \(\gamma_{q\{2\}}(G)= | K| + \omega(\phi)\).
In this section, firstly we show that for any vertex \(v \in V(H)\) there are six possible expressions, in terms of domination parameters of the factor graphs, for the \(\{2\}\)-domination number of the rooted product graph \(G \circ_v H\). Secondly, we characterize the graphs \(G\) and \(H\) that satisfy each of these expressions
Proposition 2.1. The following statements hold for graphs \(G\) and \(H\) with no isolated vertex, and any \(v \in V(H)\).
(i) \(\gamma_{\{2\}}(G \circ_v H) \leq n(G)\gamma_{\{2\}}(H)\).
(ii) If \(v \in \mathcal{S}(H)\), then \(\gamma_{\{2\}}(G \circ_v H) = n(G)\gamma_{\{2\}}(H)\).
(iii) If \(v \in V(H) \setminus \mathcal{S}(H)\), then \(\gamma_{\{2\}}(G \circ_v H) \leq \gamma_{\{2\}}(G) + n(G)\gamma_{\{2\}}(H – v)\).
Proof. (i) Let \(f\) be a \(\gamma_{\{2\}}(H)\)-function, and let \(g : V(G \circ_v H) \rightarrow \{0,1,2\}\) be a function such that \(g_x\) is the function on \(H_x\) induced by \(f\) for each \(x \in V(G)\). Then it is easy to see that \(g\) is a \(\{2\}\)DF of \(G \circ_v H\). This implies that \(\gamma_{\{2\}}(G \circ_v H) \leq \omega(g) = \sum\limits_{x \in V(G)}\omega(f_x) = n(G)\gamma_{\{2\}}(H)\).
(ii) Let \(f(A_0,A_1,A_2)\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function, and let \(x \in V(G)\). Assume that \(v \in \mathcal{S}(H)\). Since \(f_x(N[y]) \geq 2\) for each \(y \in \mathcal{L}(H_x) \cap N(x)\), \(f_x\) is a \(\{2\}\)DF of \(H_x\). This implies that \(\omega(f_x) \geq \gamma_{\{2\}}(H)\). Thus, \(\gamma_{\{2\}}(G \circ_v H) = \omega(f) = \sum\limits_{x \in V(G)}\omega(f_x) \geq n(G)\gamma_{\{2\}}(H)\). By (i), the equality follows.
(iii) Assume that \(v \in V(H) \setminus \mathcal{S}(H)\). Let \(f\) be a \(\gamma_{\{2\}}(H – v)\)-function, and let \(g\) be a function on \((G \circ_v H) \setminus V(G)\) such that \(g|_{H_x – x}\) is the function on \(H_x – x\) induced by \(f\) for each \(x \in V(G)\). For any \(\gamma_{\{2\}}(G)\)-function \(h\), it follows that \(g \cup h\) is a \(\{2\}\)DF of \(G \circ_v H\). Thus, \(\gamma_{\{2\}}(G \circ_v H) \leq \omega(g \cup h) = \gamma_{\{2\}}(G) + n(G)\gamma_{\{2\}}(H – v)\). ◻
By Proposition 2.1(ii), we consider rooted product graphs where the root vertex is not a support vertex.
Lemma 2.2. Let \(H\) be a graph with no isolated vertex. If \(v \in V(H) \setminus \mathcal{S}(H)\), then \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H) -2\). Furthermore, if \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -2\), then \(N(v) \cap (A_1 \cup A_2) =\emptyset\) for every \(\gamma_{\{2\}}(H – v)\)-function \(f(A_0,A_1,A_2)\).
Proof. Let \(v \in V(H) \setminus \mathcal{S}(H)\), and let \(f(A_0,A_1,A_2)\) be a \(\gamma_{\{2\}}(H – v)\)-function. For every \(u \in N(v)\), the function \(g(A_0,A_1 \cup \{v, u\},A_2)\) is a \(\{2\}\)DF of \(H\). Thus, \(\gamma_{\{2\}}(H) -2 \leq \omega(g) -2 \leq \omega(f) = \gamma_{\{2\}}(H – v)\).
Assume that \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -2\). If there exists a vertex \(u \in (A_1 \cup A_2) \cap N(v)\), then \(h(A_0,A_1 \cup \{v\},A_2)\) is a \(\{2\}\)DF of \(H\), a contradiction. Thus, \(N(v) \cap (A_1 \cup A_2) =\emptyset\). ◻
Lemma 2.3. If \(f\) is a \(\gamma_{\{2\}}(G \circ_v H)\)-function and \(x \in V(G)\), then \(\omega(f_x) \geq \gamma_{\{2\}}(H) -2\). Furthermore, if \(\omega(f_x) = \gamma_{\{2\}}(H) -2\), then \(f(N_H[x]) =0\).
Proof. Let \(f(A_0,A_1,A_2)\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function and \(x \in V(G)\). Define a function \(f'\) on \(H_x\) by \(f'(x)=2\) and \(f'(v)=f_x^{-}(v)\) for \(v \in V(H_x) \setminus \{x\}\). Then \(f'\) is a \(\{2\}\)DF of \(H_x\). Thus, \(\gamma_{\{2\}}(H) -2 = \gamma_{\{2\}}(H_x) -2 \leq \omega(f')-2 \leq \omega(f_x)\).
Let \(x\) be a vertex of \(V(G)\) such that \(\omega(f_x) = \gamma_{\{2\}}(H) -2\). Suppose that there exists \(y \in V(G)\) such that \(y \in N_{H_x}[x] \cap (A_1 \cup A_2)\). If \(f(y)=2\), then clearly \(f_x\) is a \(\gamma_{\{2\}}(H_x)\)-function, a contradiction. If \(f(y)=1\), then the function replaced the value of \(f(y)\) by \(2\) is a \(\{2\}\)DF of \(H_x\) with the weight \(\gamma_{\{2\}}(H) -1\), a contradiction. Thus, we have \(f(N_H[x]) =0\). ◻
For every \(\gamma_{\{2\}}(G \circ_v H)\)-function \(f\), define the following sets
\[\mathcal{A}_f = \{ x \in V(G) : \omega(f_x) \geq \gamma_{\{2\}}(H) \},\]
\[\mathcal{B}_f = \{ x \in V(G) : \omega(f_x) = \gamma_{\{2\}}(H) -1 \},\] and \[\mathcal{C}_f = \{ x \in V(G) : \omega(f_x) = \gamma_{\{2\}}(H) -2 \}.\]
Lemma 2.4. Given a \(\gamma_{\{2\}}(G \circ_v H)\)-function \(f(A_0,A_1,A_2)\) with \(\mathcal{B}_f \not= \emptyset\) and \(\mathcal{C}_f = \emptyset\), the following statements hold.
(i) If \(\mathcal{B}_f \cap (A_1 \cup A_2) \not= \emptyset\), then \(\gamma_{\{2\}}(G \circ_v H) = n(G)(\gamma_{\{2\}}(H) -1)\).
(ii) If \(\mathcal{B}_f \cap (A_1 \cup A_2) = \emptyset\), then \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -1\), and \(\gamma(G) +n(G)(\gamma_{\{2\}}(H)-1) \leq \gamma_{\{2\}}(G \circ_v H) \leq \gamma_{q\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -1)\).
Proof. (i) Let \(z \in \mathcal{B}_f \cap (A_1 \cup A_2)\), and let \(g\) be a function on \(G \circ_v H\) such that \(g_x\) is the function on \(H_x\) induced by \(f_z\) for each \(x \in V(G)\). Then it is easy to see that \(g\) is a \(\{2\}\)DF of \(G \circ_v H\). This implies that \(\gamma_{\{2\}}(G \circ_v H) \leq \omega(g) = \sum\limits_{x \in V(G)}\omega(g_x) = n(G)(\gamma_{\{2\}}(H) -1)\). Since \(\mathcal{C}_f = \emptyset\), we deduce that \(\gamma_{\{2\}}(G \circ_v H) = \omega(f) \geq n(G)(\gamma_{\{2\}}(H) -1)\). The equality follows.
(ii) Let \(z \in \mathcal{B}_f\). Since \(z \not\in (A_1 \cup A_2)\), we deduce that \(z \not\in \mathcal{S}(H_z)\), which implies that \(f_z\) is a \(\{2\}\)DF of \(H_z -z\). Thus, \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H_z – z) \leq \omega(f_z) = \gamma_{\{2\}}(H)-1\). By Lemma 2.2, it follows from the above inequality that \(\gamma_{\{2\}}(H – v) \in \{ \gamma_{\{2\}}(H)-1, \gamma_{\{2\}}(H) -2 \}\).
If \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -2\), then by Proposition 2.1(iii) and \(\mathcal{C}_f = \emptyset\), we have that \(n(G)(\gamma_{\{2\}}(H) -1) \leq \gamma_{\{2\}}(G \circ_v H) \leq \gamma_{\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -2)\), which implies that \(\gamma_{\{2\}}(G \circ_v H) = n(G)(\gamma_{\{2\}}(H) -1)\) and so \(\mathcal{B}_f = V(G)\). Since \(\mathcal{B}_f \cap (A_1 \cup A_2) = \emptyset\), this implies that \(f_x\) is a \(\{2\}\)DF of \(H\) with the weight \(\gamma_{\{2\}}(H) -1\), a contradiction. Thus, \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -1\).
Now, we prove the upper bound of \(\gamma_{\{2\}}(G \circ_v H)\). Let \((K, \phi)\) be a \(\gamma_{q\{2\}}(G)\)-pair, \(h\) a \(\gamma_{\{2\}}(H – v)\)-function and \(g\) a \(\gamma_{\{2\}}(H)\)-function. We construct a \(\{2\}\)DF \(f\) of \(G \circ_v H\) as follows. If \(x \in K\), then \(f_x\) is equal to \(g\). If \(x \in V(G) \setminus K\), then \(f_x^-\) is equal to \(h\). The \(f|_{V(G) \setminus K}\) is defined to be the \(\gamma_{\{2\}}(G -K)\)-function \(\phi\). Then it is easy to see that \(f\) is a \(\{2\}\)DF of \(G \circ_v H\), which implies that
\[\begin{aligned} \gamma_{\{2\}}(G \circ_v H) \leq \omega(f) = & | K| \gamma_{\{2\}}(H) + \omega(\phi) +(n(G)-| K|)(\gamma_{\{2\}}(H) -1) \\ = & \gamma_{q\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -1). \end{aligned}\]
We prove the lower bound of \(\gamma_{\{2\}}(G \circ_v H)\). Note that \(f_x(N[x]) \leq 1\) for each \(x \in \mathcal{B}_f\), which implies that \(\mathcal{A}_f\) is a dominating set of \(G\). Thus, \[\begin{aligned} \gamma_{\{2\}}(G \circ_v H) = & \sum\limits_{x \in \mathcal{A}_f} \omega(f_x) + \sum\limits_{x \in \mathcal{B}_f} \omega(f_x) \\ \geq& |\mathcal{A}_f| \gamma_{\{2\}}(H) + |\mathcal{B}_f | (\gamma_{\{2\}}(H)-1) \\ \geq& |\mathcal{A}_f | +n(G)(\gamma_{\{2\}}(H)-1) \\ \geq& \gamma(G) +n(G)(\gamma_{\{2\}}(H)-1). \end{aligned}\] ◻
Theorem 2.5. Let \(G\) and \(H\) be graphs with no isolated vertex. If \(v \in V(H)\), then \(\gamma_{\{2\}}(G \circ_v H) \in \{ n(G)\gamma_{\{2\}}(H), n(G)(\gamma_{\{2\}}(H) -1), \gamma(G) + n(G)(\gamma_{\{2\}}(H)-1), \gamma_{I}(G) +n(G)(\gamma_{\{2\}}(H) -1), \gamma_{q\{2\}}(G) \) \(+n(G)(\gamma_{\{2\}}(H) -1), \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) -2)\}\).
Proof. Let \(f(A_0, A_1, A_2)\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function, and let \(\mathcal{A}_f, \mathcal{B}_f\) and \(\mathcal{C}_f\) be the subsets of \(V(G)\) defined above. We consider the following cases.
Case 1. \(\mathcal{B}_f \cup \mathcal{C}_f = \emptyset\). Then \(\mathcal{A}_f = V(G)\) and so \(\gamma_{\{2\}}(G \circ_v H) \geq n(G)\gamma_{\{2\}}(H)\). By Proposition 2.1(i), we have that \(\gamma_{\{2\}}(G \circ_v H) = n(G)\gamma_{\{2\}}(H)\).
Case 2. \(\mathcal{B}_f \not= \emptyset\) and \(\mathcal{C}_f = \emptyset\). If \(\mathcal{B}_f \cap (A_1 \cup A_2) \not= \emptyset\), then it follows from Lemma 2.4(i) that \(\gamma_{\{2\}}(G \circ_v H) = n(G)(\gamma_{\{2\}}(H) -1)\).
From now on, assume that \(\mathcal{B}_f \cap (A_1 \cup A_2) = \emptyset\) in Case 2. Observe that if \(x \in \mathcal{B}_f\), then \(f(M) \leq 1\), where \(M: =N_{H_x}(x) \cap (A_1 \cup A_2)\). Otherwise, \(f_x\) is a \(\{2\}\)DF of \(H_x\) with the weight less than \(\gamma_{\{2\}}(H)\), a contradiction.
Now we define the following subsets. Let \(\mathcal{B}_f' = \{ x \in \mathcal{B}_f : |N_{H_x}(x) \cap A_1| = 1\}\) and \(\mathcal{B}_f'' = \{ x \in \mathcal{B}_f : |N_{H_x}(x) \cap A_1| = 0\}\), and let \(\mathcal{A}_f' = \{ x \in \mathcal{A}_f : \omega(f_x)= \gamma_{\{2\}}(H) \}\) and \(\mathcal{A}_f'' = \{ x \in \mathcal{A}_f : \omega(f_x) \geq \gamma_{\{2\}}(H) +1 \}\). Note that \(\mathcal{A}_f'' \subseteq (A_1 \cup A_2)\). We consider the following three subcases in Case 2.
Subcase 2.1. \(\mathcal{B}_f' \not= \emptyset\).
Let \(y \in \mathcal{B}_f'\). Define a function \(g : V(G \circ_v H) \rightarrow \{0,1,2\}\) by \(g_x^{-} = f_y^{-}\) for each \(x \in V(G)\) and \(g|_{V(G)}\) is a \(\{0, 1\}\)-function such that the inverse image of \(1\) is a minimum dominating set of \(G\). Then \(g\) is a \(\{2\}\)DF of \(G \circ_v H\). It follows that \(\omega(g) = \gamma(G) + n(G)(\gamma_{\{2\}}(H) -1) \geq \gamma_{\{2\}}(G \circ_v H)\). By the lower bound of Lemma 2.4(ii), we have \(\gamma_{\{2\}}(G \circ_v H) = \gamma(G) + n(G)(\gamma_{\{2\}}(H)-1)\).
Subcase 2.2. \(\mathcal{B}_f' = \emptyset\) and there exists \(z \in \mathcal{A}_f'\) such that \(f_z\) is a \(\gamma_{\{2\}}(H_z)\)-function with \(f(z) >0\).
Subcase 2.2.1. There exists no \(z \in \mathcal{A}_f'\) such that \(f_z\) is a \(\gamma_{\{2\}}(H_z)\)-function with \(f(z)=2\). This implies that \(\omega(f_u)= \gamma_{\{2\}}(H)+1\) for \(u \in \mathcal{A}_f''\).
To construct a \(\{2\}\)DF of \(G \circ_v H\), let \(v \in \mathcal{B}_f\), and let \(y \in \mathcal{A}_f'\) such that \(f_y\) is a \(\gamma_{\{2\}}(H_y)\)-function with \(f(y) =1\). Let \(s \in \mathcal{A}_f''\), and let \((B_0,B_1,B_2)\) be a \(\gamma_{I}(G)\)-function. Without loss of generality, we can assume that \(f(s)=2\). Define a function \(g\) on \(G \circ_v H\) by \(g_x = f_y\) for \(x \in B_1\), \(g_x = f_s\) for \(x \in B_2\) and \(g_x = f_v\) for \(x \in B_0\). Then \(g\) is a \(\{2\}\)DF of \(G \circ_v H\). Thus, \[\begin{aligned} \gamma_{\{2\}}(G \circ_v H) \leq& \sum\limits_{x \in B_0} \omega(g_x) + \sum\limits_{x \in B_1} \omega(g_x) + \sum\limits_{x \in B_2} \omega(g_x) \\ = & |B_0|(\gamma_{\{2\}}(H)-1) +|B_1|\gamma_{\{2\}}(H) +|B_2|(\gamma_{\{2\}}(H)+1) \\ = & |B_1|+ 2|B_2| +n(G)(\gamma_{\{2\}}(H)-1)\\ = & \gamma_{I}(G) + n(G)(\gamma_{\{2\}}(H)-1). \end{aligned}\]
Since \(\mathcal{B}_f =\mathcal{B}_f''\), it follows that \(\mathcal{B}_f \cap (A_1 \cup A_2) = \emptyset\). This condition and \(\mathcal{C}_f = \emptyset\) imply that \(f|_{V(G)}\) is a \(I\)DF of \(G\). So, \(\gamma_{I}(G) \leq \omega(f|_{V(G)}) \leq |\mathcal{A}_f'| +2|\mathcal{A}_f''|\). Thus, \[\begin{aligned} \gamma_{\{2\}}(G \circ_v H) = & \sum\limits_{x \in \mathcal{A}_f'} \omega(f_x) + \sum\limits_{x \in \mathcal{A}_f''} \omega(f_x) + \sum\limits_{x \in \mathcal{B}_f} \omega(f_x) \\ \geq& |\mathcal{A}_{f}'|\gamma_{\{2\}}(H) +|\mathcal{A}_{f}''|(\gamma_{\{2\}}(H)+1) +|\mathcal{B}_{f}|(\gamma_{\{2\}}(H)-1) \\ = & |\mathcal{A}_{f}'| +2|\mathcal{A}_{f}''| + n(G)(\gamma_{\{2\}}(H)-1)\\ \geq& \gamma_{I}(G) +n(G)(\gamma_{\{2\}}(H) -1). \end{aligned}\] It follows from the above inequalities that \(\gamma_{\{2\}}(G \circ_v H) = \gamma_{I}(G) + n(G)(\gamma_{\{2\}}(H)-1)\).
Subcase 2.2.2. There exists \(z \in \mathcal{A}_f'\) such that \(f_z\) is a \(\gamma_{\{2\}}(H_z)\)-function with \(f(z)=2\).
Without loss of generality, we can assume that \(f(x)=2\) for \(x \in \mathcal{A}_f\). Let \(y \in \mathcal{B}_f''\).
Define a function \(g\) by \(g_x = f_z\) for \(x \in X\), where \(X\) is a minimum dominating set of \(G\), and \(g_x = f_y\) for \(x \in V(G) \setminus X\). Then \(g\) is a \(\{2\}\)DF of \(G \circ_v H\). Thus, \[\begin{aligned} \gamma_{\{2\}}(G \circ_v H) \leq& \sum\limits_{x \in X} \omega(g_x) + \sum\limits_{x \in V(G) \setminus X} \omega(g_x) \\ = & |X|(\gamma_{\{2\}}(H)) +|V(G) \setminus X|(\gamma_{\{2\}}(H)-1) \\ = & |X| +n(G)(\gamma_{\{2\}}(H)-1)\\ = & \gamma(G) + n(G)(\gamma_{\{2\}}(H)-1). \end{aligned}\]
Since \(\mathcal{B}_f =\mathcal{B}_f''\), it follows that \(\mathcal{B}_f \cap (A_1 \cup A_2) = \emptyset\). This condition and \(\mathcal{C}_f = \emptyset\) imply that \(\mathcal{A}_f\) is a dominating set of \(G\). So, \(\gamma(G) \leq |\mathcal{A}_f|\). Thus,
\[\begin{aligned} \gamma_{\{2\}}(G \circ_v H) = & \sum\limits_{x \in \mathcal{A}_f} \omega(f_x) + \sum\limits_{x \in \mathcal{B}_f} \omega(f_x) \\ \geq& |\mathcal{A}_f|(\gamma_{\{2\}}(H) +|\mathcal{B}_f|(\gamma_{\{2\}}(H)-1) \\ = & |\mathcal{A}_f| +n(G)(\gamma_{\{2\}}(H)-1)\\ \geq& \gamma(G) + n(G)(\gamma_{\{2\}}(H)-1). \end{aligned}\]
It follows from the above inequalities that \(\gamma_{\{2\}}(G \circ_v H) = \gamma(G) + n(G)(\gamma_{\{2\}}(H)-1)\).
Subcase 2.3. \(\mathcal{B}_f' = \emptyset\), and
(1) \(\mathcal{A}_f' = \emptyset\) or (2) for any \(x \in \mathcal{A}_f'\), either \(f_x\) is not a \(\gamma_{\{2\}}(H_x)\)-function or \(x \in A_0\).
Note that the condition (2) means that \(\mathcal{A}_f' \not= \emptyset\) and every \(x \in \mathcal{A}_f'\) satisfies one of the following statements.
(a) \(f_x\) is a \(\gamma_{\{2\}}(H_x)\)-function such that \(x \in A_0\).
(b) \(f_x\) is not a \(\{2\}\)DF of \(H_x\) and \(x \in A_1\).
(c) \(f_x\) is not a \(\{2\}\)DF of \(H_x\) and \(x \in A_0\).
Since (c) is can be replaced by (a), we only assume the cases of (a) and (b).
Let \(\mathcal{A}_{f,0}' = \{ x \in \mathcal{A}_f' \mid x ~\text{satisfies the condition (a)} \}\). Define a function \(h : V(G) \setminus \mathcal{A}_{f,0}' \rightarrow \{0, 1\}\) by \(h(x) =0\) for \(x \in \mathcal{B}_f\), \(h(x) =1\) for \(\mathcal{A}_f' \setminus \mathcal{A}_{f,0}'\), \(h(x)=1\) for every \(x \in \mathcal{A}_f''\) with \(N(x) \cap (A_1 \cup A_2) \not= \emptyset\) and \(h(x)=2\) for every \(x \in \mathcal{A}_f''\) with \(N(x) \cap (A_1 \cup A_2) = \emptyset\). Then it is easy to see that \(h\) is a \(\{2\}\)DF of \(G – \mathcal{A}_{f,0}'\). This implies that \((\mathcal{A}_{f,0}', h)\) is a quasi \(\{2\}\)-dominating pair of \(G\). So, \(\gamma_{q\{2\}}(G) \leq |\mathcal{A}_{f,0}'| + \omega(h) \leq |\mathcal{A}_{f,0}'| + (|\mathcal{A}_f' \setminus \mathcal{A}_{f,0}'| + 2|\mathcal{A}_f''|) = |\mathcal{A}_{f}'| + 2|\mathcal{A}_f''|\). Thus,
\[\begin{aligned} \gamma_{\{2\}}(G \circ_v H) = & \sum\limits_{x \in \mathcal{A}_f''}\omega(f_x) + \sum\limits_{x \in \mathcal{A}_f'}\omega(f_x) + \sum\limits_{x \in \mathcal{B}_f}\omega(f_x) \\ \geq& |\mathcal{A}_f''|(\gamma_{\{2\}}(H) +1) + |\mathcal{A}_f'|\gamma_{\{2\}}(H) + |\mathcal{B}_f|(\gamma_{\{2\}}(H)-1) \\ = & 2|\mathcal{A}_f''| + |\mathcal{A}_{f}'| + n(G)(\gamma_{\{2\}}(H)-1) \\ \geq& \gamma_{q\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) – 1). \end{aligned}\]
It follows from Lemma 2.4(ii) that \(\gamma_{\{2\}}(G \circ_v H) = \gamma_{q\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) – 1)\).
Case 3. \(\mathcal{C}_f \not= \emptyset\). Let \(x \in \mathcal{C}_f\). By Lemma 2.3, \(f(N_H[x]) =0\). This implies that \(v \not\in \mathcal{S}(H)\). So, \(f_x^{-}\) is a \(\{2\}\)DF of \(H_x -x\). Thus, \(\gamma_{\{2\}}(H -v) = \gamma_{\{2\}}(H_x -x) \leq \omega(f_x^{-}) = \gamma_{\{2\}}(H) -2\). It follows from Lemma 2.2 that \(\gamma_{\{2\}}(H -v) = \gamma_{\{2\}}(H) -2\).
Now, to prove that \(\omega(f) \geq \gamma_{\{2\}}(G) + n(G)(\gamma_{\{2\}}(H)-2)\), we show that \(g(\mathcal{C}_f, \mathcal{B}_f, \mathcal{A}_f)\) is a \(\{2\}\)DF of \(G\). If \(x \in \mathcal{C}_f\), then \(f_x(N[x])=0\). So, \(f(N(x) \cap V(G)) \geq 2\), which implies that \(g(N[x]) \geq 2\). If \(x \in \mathcal{A}_f\), then clearly \(g(N[x]) \geq 2\). Assume that \(x \in \mathcal{B}_f\). Note that \(f(x) \not= 2\) for each \(x \in \mathcal{B}_f\). Then either \(f_x(N(x))=0\) or \(f_x(N(x))=1\) and \(f_x(x)=0\), since \(f_x\) is not a \(\{2\}\)DF of \(H_x\). In either case, \(N(x) \cap (\mathcal{A}_f \cup \mathcal{B}_f) \not= \emptyset\) and so \(g(N[x]) \geq 2\). Thus, \[\begin{aligned} \gamma_{\{2\}}(G \circ_v H) = & \sum\limits_{x \in \mathcal{A}_f} \omega(f_x) + \sum\limits_{x \in \mathcal{B}_f} \omega(f_x) + \sum\limits_{x \in \mathcal{C}_f} \omega(f_x) \\ \geq& |\mathcal{A}_{f}|\gamma_{\{2\}}(H) +|\mathcal{B}_{f}|(\gamma_{\{2\}}(H)-1) +|\mathcal{C}_{f}|(\gamma_{\{2\}}(H)-2) \\ \geq& 2|\mathcal{A}_{f}| +|\mathcal{B}_{f}| + n(G)(\gamma_{\{2\}}(H)-2)\\ \geq& \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) -2). \end{aligned}\]
By Proposition 2.1(iii) and the above fact that \(\gamma_{\{2\}}(H -v) = \gamma_{\{2\}}(H) -2\), we have \(\gamma_{\{2\}}(G \circ_v H) = \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) -2)\). ◻
Lemma 2.6. Let \(f\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function and assume that \(\gamma_{\{2\}}(G) < n(G)\). Then \(\mathcal{C}_f \not= \emptyset\) if and only if \(\gamma_{\{2\}}(H -v) = \gamma_{\{2\}}(H) -2\).
Proof. Let \(x \in \mathcal{C}_f\). Then \(f(N_H[x])=0\) by Lemma 2.3. This implies that \(f_x\) is a \(\{2\}\)DF of \(H_x – x\), since \(x \not\in \mathcal{S}(H_x)\). Thus, \(\gamma_{\{2\}}(H -v) = \gamma_{\{2\}}(H_x -x) \leq \omega(f_x) = \gamma_{\{2\}}(H) -2\). By Lemma 2.2, the equality follows.
If \(\gamma_{\{2\}}(H -v) = \gamma_{\{2\}}(H) -2\), then it follows from Proposition 2.1(iii) that \(\omega(f) \leq \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H)-2)\). Since \(\gamma_{\{2\}}(G) < n(G)\), it follows from Lemma 2.3 that \(\mathcal{C}_f \not= \emptyset\). ◻
Theorem 2.7. Assume that \(\gamma_{\{2\}}(G) < n(G)\). Then the following statements are equivalent.
(i) \(\gamma_{\{2\}}(G \circ_v H) = \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) -2)\).
(ii) \(\gamma_{\{2\}}(H -v) = \gamma_{\{2\}}(H) -2\).
Proof. Assume that (ii) holds. Let \(f\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function. By Lemma 2.6, (ii) is equivalent to \(\mathcal{C}_f \not= \emptyset\). By Case 3 of the proof of Theorem 2.5, (i) holds.
Conversely, assume that (i) holds. Then \(\omega(f) = \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) -2) < n(G) + n(G)(\gamma_{\{2\}}(H) -2) = n(G)(\gamma_{\{2\}}(H) -1)\), which implies that \(\mathcal{C}_f \not= \emptyset\). Thus, it follows from Lemma 2.6 that (ii) holds. ◻
Theorem 2.8. Let \(G\) and \(H\) be graphs with no isolated vertex and \(v \in V(H)\). Then \(\gamma_{\{2\}}(G \circ_v H) = n(G)(\gamma_{\{2\}}(H) -1)\) if and only if one of the following conditions holds.
(i) \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -2\) and \(\gamma_{\{2\}}(G) = n(G)\).
(ii) \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H) -1\) and there exists a \(\{2\}\)DF \(h(B_0,B_1,B_2)\) on \(H – N[v]\) with the weight \(\gamma_{\{2\}}(H) -2\) such that \(B_1 \cup B_2\) is a dominating set of \(H – v\).
Proof. Assume that \(\gamma_{\{2\}}(G \circ_v H) = n(G)(\gamma_{\{2\}}(H) -1)\). Let \(f(A_0,A_1,A_2)\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function. By Proposition 2.1(ii), we deduce that \(v \in V(H) \setminus \mathcal{S}(H)\). It follows from Lemma 2.2 that \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H) -2\). We consider the following cases.
Case 1. \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -2\). By Proposition 2.1, \(\omega(f) \leq \gamma_{\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -2)\). This implies that \(\gamma_{\{2\}}(G) =n(G)\). Thus, (i) holds.
Case 2. \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H) -1\). If \(\mathcal{C}_f \not= \emptyset\), then it follows from Lemma 2.3 that \(f(N_H[x]) =0\) for \(x \in \mathcal{C}_f\). This implies that \(v \not\in \mathcal{S}(H)\). So, \(f_x^{-}\) is a \(\{2\}\)DF of \(H_x -x\) and \(\gamma_{\{2\}}(H -v) = \gamma_{\{2\}}(H_x -x) \leq \omega(f_x^{-}) = \gamma_{\{2\}}(H) -2\). It follows from Lemma 2.2 that \(\gamma_{\{2\}}(H -v) = \gamma_{\{2\}}(H) -2\), a contradiction. Thus, \(\mathcal{C}_f = \emptyset\), which implies that \(\mathcal{B}_f = V(G)\). By Lemma 2.4, there exists \(x \in V(G) \cap A_1\). If \(N_H(x) \cap (A_1 \cup A_2) \not= \emptyset\), then \(f_x\) is a \(\{2\}\)DF of \(H_x\), a contradiction. Thus, \(N_H(x) \subseteq A_0\) and \(f|_{V(H_x) \setminus N[x]}\) is a \(\{2\}\)DF on \(H – N[x]\) with the weight \(\gamma_{\{2\}}(H) -2\), and \((V(H_x) \setminus \{x\}) \cap (A_1 \cup A_2)\) is a dominating set of \(H_x – x\). Thus, (ii) holds.
Conversely, assume that one of the conditions (i) and (ii) holds. First, suppose that (i) holds. By Proposition 2.1(iii) and the first condition of (i), \(\gamma_{\{2\}}(G \circ_v H) \leq \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) -2)\). By Theorem 2.5 and \(\gamma_{\{2\}}(G) = n(G)\), \(\gamma_{\{2\}}(G \circ_v H) = \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) -2) = n(G)(\gamma_{\{2\}}(H) -1)\).
Second, suppose that (ii) holds. Let \(h(B_0,B_1,B_2)\) be a \(\{2\}\)DF on \(H – N[v]\) with the weight \(\gamma_{\{2\}}(H) -2\). Define \(g\) on \(G \circ_v H\) by \(g_x = (V(H_x) \setminus (B_1 \cup \{x\}\cup B_2) , B_1 \cup \{x\}, B_2)\) for each \(x \in V(G)\). Then \(g\) is a \(\{2\}\)DF of \(G \circ_v H\) and so \(\gamma_{\{2\}}(G \circ_v H) \leq \omega(g) = n(G)(\omega(h) +1) =n(G)(\gamma_{\{2\}}(H) -1)\). By Theorem 2.5, \(\gamma_{\{2\}}(G \circ_v H) \in \{ n(G)(\gamma_{\{2\}}(H) -1), \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) -2) \}\). If \(\gamma_{\{2\}}(G) = n(G)\), then we are done. If \(\gamma_{\{2\}}(G) < n(G)\), then it follows from Theorem 2.7 and the first condition of (ii) that \(\gamma_{\{2\}}(G \circ_v H) \not= \gamma_{\{2\}}(G) +n(G)(\gamma_{\{2\}}(H) -2)\). Thus, \(\gamma_{\{2\}}(G \circ_v H) = n(G)(\gamma_{\{2\}}(H) -1)\). ◻
Proposition 2.9. Let \(G\) be a graph such that \(\gamma_{\{2\}}(G) < n(G)\). Let \(H\) be a graph with no isolated vertex and \(v \in V(H) \setminus \mathcal{S}(H)\). If \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H)\), then \(\gamma_{\{2\}}(G \circ_v H) \in \{n(G)(\gamma_{\{2\}}(H) -1), n(G)\gamma_{\{2\}}(H) \}\).
Proof. Let \(f(A_0,A_1,A_2)\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function. It follows from Theorem 2.5 that \(\omega(f) \leq n(G)\gamma_{\{2\}}(H)\). If \(\omega(f) = n(G)\gamma_{\{2\}}(H)\), then we are done. Suppose that \(\omega(f) < n(G)\gamma_{\{2\}}(H)\). Then \(\mathcal{C}_f = \emptyset\) by Lemma 2.6. If \(\mathcal{B}_f = \emptyset\), then \(V(G) = \mathcal{A}_f\), a contradiction to \(\omega(f) < n(G)\gamma_{\{2\}}(H)\). Thus, \(\mathcal{B}_f \not= \emptyset\). By Lemma 2.4 and \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H)\), \(\mathcal{B}_f \cap (A_1 \cup A_2) \not= \emptyset\) and so \(\omega(f)=n(G)(\gamma_{\{2\}}(H) -1)\). ◻
Proposition 2.10. Let \(G\) be a graph such that \(\gamma_{\{2\}}(G) < n(G)\). Let \(H\) be a graph with no isolated vertex and \(v \in V(H) \setminus \mathcal{S}(H)\). If \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H)\) and \(g(v)=0\) for any \(\gamma_{\{2\}}(H)\)-function \(g\), then \(\gamma_{\{2\}}(G \circ_v H) = n(G)\gamma_{\{2\}}(H)\).
Proof. By Proposition 2.9, \(\gamma_{\{2\}}(G \circ_v H)\) is either \(n(G)\gamma_{\{2\}}(H)\) or \(n(G)(\gamma_{\{2\}}(H)-1)\). Let \(f(A_0,A_1,A_2)\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function, and suppose that \(\omega(f)=n(G)(\gamma_{\{2\}}(H)-1)\). Since \(\gamma_{\{2\}}(G) < n(G)\), if \(\mathcal{C}_f \not= \emptyset\), then by Lemma 2.6 we can construct a \(\{2\}\)DF of \(G \circ_v H\) with the weight \(\gamma_{\{2\}}(G) + n(G)(\gamma_{\{2\}}(H)-2)\) less than \(n(G)(\gamma_{\{2\}}(H)-1)\), a contradiction. Thus, \(\mathcal{C}_f= \emptyset\), which implies that \(\mathcal{B}_f \not= \emptyset\). By Lemma 2.4 and \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H)\), let \(x \in \mathcal{B}_f \cap A_1\). Define a function \(g : V(H_x) \rightarrow \{0,1,2\}\) by \(g(x)=2\) and \(g(y)=f(y)\) for \(y \in V(H_x) \setminus \{x\}\). Then \(g\) is a \(\gamma_{\{2\}}(H)\)-function satisfying \(g(x)=2\), a contradiction. Thus, \(\gamma_{\{2\}}(G \circ_v H) = n(G)\gamma_{\{2\}}(H)\). ◻
Theorem 2.11. Let \(G\) be a graph such that \(\gamma_{\{2\}}(G) < n(G)\). Let \(H\) be a graph with no isolated vertex and \(v \in V(H)\). Then \(\gamma_{\{2\}}(G \circ_v H) = n(G)\gamma_{\{2\}}(H)\) if and only if either \(v \in \mathcal{S}(H)\) or the following conditions holds.
(i) \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H)\).
(ii) If \(H -N[v]\) has no isolated vertex, then there exists no \(\{2\}\)DF on \(H – N[v]\) with the weight \(\gamma_{\{2\}}(H) -2\).
Proof. Assume that \(\gamma_{\{2\}}(G \circ_v H) = n(G)\gamma_{\{2\}}(H)\). If \(v \in \mathcal{S}(H)\), then we are done. Now, assume that \(v \in V(H) \setminus \mathcal{S}(H)\). By Lemma 2.2 and Theorem 2.7, \(\gamma_{\{2\}}(H – v) \geq \gamma_{\{2\}}(H)-1\).
If \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H)-1\), then \(\gamma_{\{2\}}(G \circ_v H) \leq \gamma_{\{2\}}(G) + n(G)(\gamma_{\{2\}}(H)-1) < n(G)\gamma_{\{2\}}(H)\) by Proposition 2.1(iii), a contradiction. Thus, (i) holds.
Assume that \(H -N[v]\) has no isolated vertex. Suppose that there exists a \(\{2\}\)DF \(h\) on \(H – N[v]\) with the weight \(\gamma_{\{2\}}(H) -2\). Define a function \(f : V(G \circ_v H) \rightarrow \{0,1,2\}\) by \(f|_{V(G)}=1\) and \(f_x^{-}\) is induced by \(h\). It is easy to see that \(f\) is a \(\{2\}\)DF of \(G \circ_v H\) with the weight \(n(G)(\gamma_{\{2\}}(H) -1)\), a contradiction. Thus, (ii) holds.
Conversely, assume that either \(v \in \mathcal{S}(H)\) or (i) and (ii) hold. If \(v \in \mathcal{S}(H)\), then \(\gamma_{\{2\}}(G \circ_v H) = n(G)\gamma_{\{2\}}(H)\) by Proposition 2.1(ii). Now, assume that (i) and (ii) hold, and let \(f\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function. Since (ii) contradicts Theorem 2.8(ii), we have \(\omega(f) \not= n(G)(\gamma_{\{2\}}(H)-1)\). By (i) and Proposition 2.9, we have \(\omega(f) = n(G)\gamma_{\{2\}}(H)\). ◻
Theorem 2.12. Let \(G\) and \(H\) be graphs with no isolated vertex and \(v \in V(H)\). Let \(f\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function. Then \(\gamma_{\{2\}}(G \circ_v H) = \gamma(G) + n(G)(\gamma_{\{2\}}(H) -1)\) if and only if
(i) \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -1\) and one of the following conditions holds.
\(\quad\)(a) For some \(x \in V(G)\),there exists a \(\gamma_{\{2\}}(H)\)-function \(f_x\) such that \(f_x(v)=2\).
\(\quad\)(b) For some \(x \in V(G)\), there exists a \(\gamma_{\{2\}}(H – v)\)-function \(f_x^{-}\) such that \(f_x^{-}(N(v)) = 1\).
(ii) There exists no \(\{2\}\)DF \(h(B_0,B_1,B_2)\) on \(H – N[v]\) with the weight \(\gamma_{\{2\}}(H) -2\) such that \(B_1 \cup B_2\) is a dominating set of \(H – v\).
Proof. Assume that \(\gamma_{\{2\}}(G \circ_v H) = \gamma(G) + n(G)(\gamma_{\{2\}}(H) -1)\). Observe that (ii) follows as a consequence of Theorems 2.7 and 2.8
Now, we prove (i). Let \(f(A_0,A_1,A_2)\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function. By the Case 3 of the proof of Theorem 2.5, we deduce that \(\mathcal{C}_f = \emptyset\). Since \(\gamma(G) < n(G)\), we have \(\mathcal{B}_f \not= \emptyset\). By Lemma 2.4, \(\mathcal{B}_f \cap (A_1 \cup A_2) = \emptyset\) and \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -1\). Thus, the first equality of (i) follows.
Let \(x \in \mathcal{B}_f\) such that \(f(N(x))\) is maximum. We consider the following cases.
Case 1. \(f(N(x))=0\). By the fact that \(f(N(x))\) is maximum, \(f(N(y))=0\) for every \(y \in \mathcal{B}_f\). This implies that \(\gamma(G) \leq |\mathcal{A}_f|\). But, \[\begin{aligned} \gamma_{\{2\}}(G \circ_v H) = & \gamma(G) + n(G)(\gamma_{\{2\}}(H)-1) \\ = & \sum\limits_{x \in \mathcal{A}_f}\omega(f_x) + \sum\limits_{x \in \mathcal{B}_f}\omega(f_x) \\ \geq& |\mathcal{A}_f|\gamma_{\{2\}}(H) + |\mathcal{B}_f|(\gamma_{\{2\}}(H)-1) \\ = & |\mathcal{A}_f| + n(G)(\gamma_{\{2\}}(H)-1). \end{aligned}\]
Thus, \(|\mathcal{A}_f| \leq \gamma(G)\) and so \(|\mathcal{A}_f| = \gamma(G)\) . By Theorem 1.1, there exists a vertex \(z \in \mathcal{A}_f\) such that \(f(z)=2\), i.e., (a) follows.
Case 2. \(f(N(x)) \geq 1\). This case implies that \(f_x^{-}\) is a \(\gamma_{\{2\}}(H – v)\)-function such that \(f_x^{-}(N(v))=1\), i.e., (b) follows
Conversely, assume that (i) and (ii) hold. By Theorems 2.5, 2.7 and 2.8, we have \(\gamma_{\{2\}}(G \circ_v H) \geq \gamma(G) + n(G)(\gamma_{\{2\}}(H) -1)\). Let \(D\) be a \(\gamma(G)\)-set.
First, assume that (a) holds. Let \(x \in V(G)\) such that \(f_x\) be a \(\gamma_{\{2\}}(H)\)-function such that \(f_x(v)=2\). Let \(h\) be the function extended from a \(\gamma_{\{2\}}(H – v)\)-function by assigning \(0\) at \(v\). Define a function \(g :V(G \circ_v H) \rightarrow \{0,1,2\}\) by \(g_y=f_x\) for \(y \in D\) and \(g_y=h\) for \(y \in V(G) \setminus D\). Then \(g\) is a \(\{2\}\)DF of \(G \circ_v H\) and so \(\gamma_{\{2\}}(G \circ_v H) \leq \omega(g) = \gamma(G) + n(G)(\gamma_{\{2\}}(H) -1)\). By Theorems 2.5 and 2.7, we have \(\gamma_{\{2\}}(G \circ_v H) = \gamma(G) + n(G)(\gamma_{\{2\}}(H) -1)\).
Second, assume that (b) holds. Let \(x \in V(G)\) such that \(f_x^{-}\) is a \(\gamma_{\{2\}}(H – v)\)-function with \(f_x^{-}(N(v)) = 1\). Define a function \(g :V(G \circ_v H) \rightarrow \{0,1,2\}\) by \(g_y^{-} = f_x^{-}\) for each \(y \in V(G)\) and \(g|_{V(G)}\) is a \(\{0, 1\}\)-function such that \(g^{-1}(1)=D\). Then \(g\) is a \(\{2\}\)DF of \(G \circ_v H\) and so \(\gamma_{\{2\}}(G \circ_v H) \leq \omega(g) = \gamma(G) + n(G)(\gamma_{\{2\}}(H) -1)\). By Theorems 2.5 and 2.7, we have \(\gamma_{\{2\}}(G \circ_v H) = \gamma(G) + n(G)(\gamma_{\{2\}}(H) -1)\). ◻
Theorem 2.13. Let \(G\) be a graph such that \(\gamma(G) < \gamma_{q\{2\}}(G) < \gamma_{\{2\}}(G) \leq n(G)\). Let \(H\) be a graph with no isolated vertex and \(v \in V(H)\). Let \(f\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function. Then \(\gamma_{\{2\}}(G \circ_v H) = \gamma_{q\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -1)\) if and only if
(i) \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -1\).
(ii) For every \(x \in
V(G)\), \(f_x^{-}\) is a \(\gamma_{\{2\}}(H – v)\)-function such that
\(f_x^{-}(N(v)) =0\).
Proof. Assume that \(\gamma_{\{2\}}(G \circ_v H) = \gamma_{q\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -1)\). Let \(f(A_0,A_1,A_2)\) be a \(\gamma_{\{2\}}(G \circ_v H)\)-function. By the Case 3 of the proof of Theorem 2.5, we deduce that \(\mathcal{C}_f = \emptyset\). As \(\gamma_{q\{2\}}(G) < n(G)\), it follows that \(\mathcal{B}_f \not= \emptyset\). By Lemma 2.4, \(\mathcal{B}_f \cap (A_1 \cup A_2) = \emptyset\) and \(\gamma_{\{2\}}(H – v) = \gamma_{\{2\}}(H) -1\), i.e., (i) follows. Note that \(N_H(x) \cap (A_1 \cup A_2) = \emptyset\) for every \(x \in \mathcal{B}_f\), otherwise we can construct a \(\{2\}\)DF of \(G \circ_v H\) with the weight \(n(G)(\gamma_{\{2\}}(H) -1)\), a contradiction.
Suppose that \(f_x^{-}\) is a \(\gamma_{\{2\}}(H – v)\)-function such that \(f_x^{-}(N(v)) =1\) for some \(x \in V(G)\). Then we can construct a \(\{2\}\)DF of \(G \circ_v H\) with the weight \(\gamma(G) + n(G)(\gamma_{\{2\}}(H) -1)\), a contradiction. Thus, (ii) follows.
Conversely, assume that (i) and (ii) hold. By Theorems 2.5, 2.7, 2.8 and 2.12, we deduce that \(\gamma_{\{2\}}(G \circ_v H) \geq \gamma_{q\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -1)\). For a \(\gamma_{q\{2\}}(G)\)-pair \((K, \phi)\), we construct a \(\{2\}\)DF \(g\) of \(G \circ_v H\) with the weight \(\gamma_{q\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -1)\) as follows.
Let \(h\) be a \(\gamma_{\{2\}}(H – v)\)-function, and let \(i\) be a \(\gamma_{\{2\}}(H)\)-function. If \(x \in K\), then \(g_x = i\). If \(x \in V(G) \setminus K\), then \(g_x\) is defined as the function extended from \(h\) by \(\phi(x)\). Since \[\begin{aligned} \omega(g) = & |K|\gamma_{\{2\}}(H) + \omega(\phi) + (n(G) – |K|) (\gamma_{\{2\}}(H) -1) \\ = & |K| + \omega(\phi) +n(G)(\gamma_{\{2\}}(H) -1) \\ = & \gamma_{q\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -1), \end{aligned}\] we have \(\gamma_{\{2\}}(G \circ_v H)= \gamma_{q\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -1).\) ◻
As proved in Theorem 2.5, there are six closed formulas for \(G \circ_v H\). Five cases were characterized in Theorems 2.7, 2.8, 2.11, 2.12 and 2.13. Thus, we can characterize the case of \(\gamma_{\{2\}}(G \circ_v H) = \gamma_{\{2\}}(G) + n(G)(\gamma_{\{2\}}(H) -1)\) by eliminating the previous ones from the family of all graphs \(G\) and \(H\) with no isolated vertices and roots \(v\) of \(H\).