Observation 2.1. If u and v are twins of a connected graph G, then every forcing set of G contains at least one vertex of $\{u,v\}$ .

Proof. We first show that the semitotal forcing problem is in NP. Given a set S of vertices of G, it can be checked in polynomial time whether there is a vertex in S with exactly one neighbour not in S. Moreover, there cannot be more than $|V|$ steps in a forcing process. Thus, a nondeterministic algorithm can check in polynomial time whether a subset of vertices of V is forcing and further semitotal forcing, and whether it has size at most $k+1$ .

To show the hardness, we give a polynomial reduction from the forcing problem, which has been shown to be NP-complete in [Reference Aazami1, Reference Chekuri, Korula, Albers, Marchetti-Spaccamela, Matias, Nikoletseas and Thomas5].

Let $G=(V,E)$ be a graph, where $V=\{v_1,\ldots , v_n\}$ . We construct a connected graph $G'=(V',E')$ with vertex set $V'=V\cup \{u,w_1,w_2\}$ and edge set

$$ \begin{align*}E'=E\cup\{uv_i \mid i\in[n]\}\cup\{uw_1,uw_2\}.\end{align*} $$

We will show that G has a forcing set of size at most k if and only if $G'$ has a semitotal forcing set of size at most k.

Suppose that G has a forcing set S of size at most k. We claim that $S'=S\cup \{w_1\}$ is a semitotal forcing set of $G'$ . First, we colour all vertices in $S'$ black and the other vertices of $G'$ white. Then $w_1\rightarrow u$ and further all vertices of $V(G)$ can be forced by applying the colour-change rule to S. Finally, $u\rightarrow w_2$ . Hence, $S'$ is a forcing set of $G'$ . Since every vertex in S is within distance 2 of the vertex $w_1$ , $S'$ is a semitotal forcing set of $G'$ of size at most $k+1$ .

Conversely, suppose that $G'$ has a semitotal forcing set $S'$ of size at most $k+1$ . By Observation 2.1, at least one vertex of $\{w_1, w_2\}$ belongs to $S'$ . Renaming vertices if necessary, we may assume that $w_1\in S'$ . We can choose a semitotal forcing set $S'$ such that u does not force any vertex of $V(G)$ . This is because if u forces a vertex v of $V(G)$ , then $w_2\in S'$ , and $S"=(S'\setminus\{w_2\}) \cup\{v\}$ is also a semitotal forcing set of $G'$ . Thus, each force between vertices of $V(G)$ in $G'$ can also be applied for $S:= S'\cap V(G)$ in G, since if $v\in V(G)$ has a single white neighbour in $G'$ at some step of the forcing process, it will have the same white neighbour in G. Moreover, since u does not force any vertex in $V(G)$ , all vertices in $V(G)$ must be forced by the vertices of $S'$ which are in $V(G)$ . Thus, S is a forcing set of G. Additionally, $|S|= |S'\cap V(G)|\leq k+1-1=k$ , so S has size at most k.

Algorithm 1 Weak partition.

Proof. Let $G\neq K_n$ be a connected graph of order $n \geq 4$ with maximum degree $\Delta \geq 2$ . If $\Delta =2$ , then $G=P_n$ or $G=C_n$ . In both cases, $F_{t2}(G)=2\leq {n}/{2}= (\Delta-1)n/\Delta $ , as desired. Further, if $F_{t2}(G)= (\Delta-1)n/\Delta$ , then $n = 4$ . Thus, $G= C_4$ or $G = P_4$ . Hence, we assume that $\Delta \geq 3$ in what follows.

Applying Algorithm 1 to $G=(V,E)$ , we get a weak partition $(A,B,C,A',B',R)$ of V, and $A=\{v_1, \ldots , v_k\}$ , $B=\{B_1, \ldots , B_k\}$ , $C=\{C_1, \ldots , C_k\}$ , $A'=\{v_{k+1}, \ldots , v_r\}$ , $B'=\{B_{k+1}, \ldots , B_r\}$ . Since $G\neq K_n$ , the sets A, B and C are not empty. For $1\leq i\leq k$ , let $G_i$ be the graph induced by $\{v_i\}\cup B_i\cup C_i$ ; for $k+1\leq i\leq r$ , let $G_i$ be the graph induced by $\{v_i\}\cup B_i$ . Note that r may be equal to k. Let $G_i$ have order $n_i$ and $|B_i| = b_i$ , $|C_i| = c_i$ . In what follows, we consider $G_i$ and divide into two cases.

Case 1: $1\leq i\leq k$ . We divide into two subcases.

Subcase 1.1: $b_i=1$ and $c_i=1$ . In this subcase, $G_i=P_3$ and $n_i=3$ . Let $S_i=\{v_i\}\cup B_i$ . Then $S_i$ is a semitotal forcing set of $G_i$ and

(4.1) $$ \begin{align} |S_i|=2=\frac{2}{3}\times 3\leq \frac{\Delta-1}{\Delta}n_i. \end{align} $$

Subcase 1.2: $b_i\geq 2$ or $c_i\geq 2$ . By Algorithm 1, we note that the set $B_i$ dominates the set $C_i$ . Let $D_i$ be a minimum set of vertices in $B_i$ that dominate $C_i$ and $|D_i| = d_i$ . Note that $1 \leq d_i \leq b_i$ . Let $D_{i}=\{x_1^i, \ldots , x_{d_i}^i\}$ . By the minimality of the set $D_i$ , each vertex $x_j^i$ in $D_i$ dominates a vertex $y_j^i$ in $C_i$ that is not dominated by the other vertices in $D_i$ , where $j\in [d_i]$ . Now, let $D^{\prime }_i=\{y_1^i, \ldots , y_{d_i}^i\}$ and $L_i=C_i\setminus D^{\prime }_i$ . Let $|L_i|= l_i$ . Then $c_i= d_i + l_i$ and $n_i = b_i + c_i +1 = b_i + d_i + l_i + 1$ . Each vertex in $D_i$ is adjacent to $v_i$ and to exactly one vertex in $D^{\prime }_i$ , and therefore is adjacent to at most $\Delta - 2$ vertices in $L_i$ , implying that $l_i \leq d_i(\Delta - 2)$ . Let $S_i= V(G_i)\setminus (D^{\prime }_i\cup \{x_1^i\})$ . By the construction, $S_i$ is semitotal. Further, the set $S_i$ is a forcing set of $G_i$ since $v_i\rightarrow x_1^i$ first, and then $x_j^i\rightarrow y_j^i$ for $j\in [d_i]$ . Thus, the set $S_i$ is a semitotal forcing set of $G_i$ . Moreover,

(4.2) $$ \begin{align} |S_i|=b_i+ l_i &\leq b_i + d_i(\Delta-2) =b_i -d_i+ d_i(\Delta-1)\nonumber\\ &\leq \Delta-1+ d_i(\Delta-1) = (d_i+1)(\Delta-1), \end{align} $$

which implies that $d_i+1\geq |S_i|/(\Delta-1)$ . Thus, $n_i=b_i+ l_i+d_i+1=|S_i|+d_i+1\geq |S_i|+|S_i|/(\Delta-1)$ and further $|S_i|\leq (\Delta-1)n_i/\Delta$ .

Case 2: $k+1\leq i\leq r$ . In this case, $G_i=G[\{v_i\}\cup \{B_i\}]$ is a complete graph. Since $G\neq K_{\Delta +1}$ , we have $2\leq b_i\leq \Delta -1$ . Let $S_i= B_i$ . It is clear that $S_i$ is a semitotal forcing set of $G_i$ . Thus, $n_i=b_i+1$ and

$$ \begin{align*} |S_i|=b_i\leq\frac{\Delta-1}{\Delta}(b_i+1)=\frac{\Delta-1}{\Delta}n_i. \end{align*} $$

The set $S_i$ constructed for each $i\in [r]$ (see Cases 1 and 2 above) is a semitotal forcing set of $G_i$ . We now let $S'=\mathop {\cup }_{i=1}^{r} S_i$ . Thus,

$$ \begin{align*} |S'|=\sum\limits_{i=1}^{r} |S_i|\leq\sum\limits_{i=1}^{r}\frac{\Delta-1}{\Delta}n_i =\frac{\Delta-1}{\Delta}\sum\limits_{i=1}^{r}n_i. \end{align*} $$

If $R=\emptyset $ , then $V(G)=\mathop {\cup }_{i=1}^{r} V(G_i)$ . We claim that $S=S'$ is a semitotal forcing set of G. As shown earlier, each set $S_i$ is a semitotal forcing set of $G_i$ for all $i\in [r]$ . By the construction, S is semitotal. We colour all vertices in S black and the other vertices white. When we apply the colour-change rule, all vertices of $G_i$ will become black in the order i and

$$ \begin{align*} |S|=|S'|\leq\frac{\Delta-1}{\Delta}\sum\limits_{i=1}^{r}n_i=\frac{\Delta-1}{\Delta}n. \end{align*} $$

Now we consider $R\neq \emptyset $ . Suppose $G[R]$ has order $n_R$ . Recall that every component of $G[R]$ is either an edge or an isolated vertex and there is no edge between R and $A\cup A'\cup B\cup B'$ . Since G is connected, every component of $G[R]$ is adjacent to some vertex of C. If there exists a vertex $v\in R$ which is not adjacent to some vertex of C, then v belongs to a $P_2$ -component of $G[R]$ and its neighbour is adjacent to some vertex of C. Take all the vertices that are the same as v and put them into T. Let $|T|=t$ and $W=R\setminus T$ . Note that $W\neq \emptyset $ . Let $D\subseteq C$ be a minimum dominating set of W and $|D|=d$ , $D=\{x_1,\ldots , x_d\}$ . By the minimality of the set D, each vertex $x_j$ in D dominates a vertex $y_j$ in W that is not dominated by the other vertices in D, where $j\in [d]$ . Let $D'=\{y_1, \ldots , y_{d}\}$ and $L=W\setminus D'$ . Let $|L|= l$ so that $n_R=d+l+t$ .

If $l=0$ , then $S=S'$ is a semitotal forcing set of G. Additionally,

$$ \begin{align*} |S|=|S'|\leq\frac{\Delta-1}{\Delta}\sum\limits_{i=1}^{r}n_i <\frac{\Delta-1}{\Delta}n. \end{align*} $$

Now assume that $l\neq 0$ . If $d(v, L\cup S')\leq 2$ for any $v\in L$ , then set $S"=L$ . Then $S=S'\cup S"$ is a semitotal forcing set of G; we will justify this claim at the end of the proof. Since each vertex in $D\ (\subseteq C)$ is adjacent to a vertex of B and to exactly one vertex in $D^{\prime }_i$ , we have $l\leq d(\Delta -2)$ . Recall that $n_R=d+l+t\geq d+l$ , so $|S"|=l\leq d(\Delta -2)\leq (n_R-|S"|)(\Delta -2)$ . This implies that $|S"|\leq ({(\Delta -2)}/{(\Delta -1)})n_R< ({(\Delta -1)}/{\Delta })n_R$ . Thus,

$$ \begin{align*} \begin{aligned} |S|=|S'|+|S"| <\frac{\Delta-1}{\Delta}\sum\limits_{i=1}^{r}n_i+\frac{\Delta-1}{\Delta}n_R =\frac{\Delta-1}{\Delta}\bigg(\sum\limits_{i=1}^{r}n_i+n_R\bigg) =\frac{\Delta-1}{\Delta}n. \end{aligned} \end{align*} $$

Suppose that there exists $v\in L$ such that $d(v, L\cup S')\geq 3$ . Take all the vertices that are the same as v and put them into X. For any $w\in X$ , there exists $u\in D$ such that u is adjacent to w and $u\in C_i$ for some i as in Subcase 1.2. Here, u is adjacent to $x_1^i$ , that is, $u=y_1^i$ and $x_1^i$ is its neighbour in $G_i$ . Since $d(w, L\cup S')\geq 3$ , we have $N_{R}(y_1^i)=\{w,w'\}$ , where $w'\in D'$ . Take all the vertices that are the same as $w'$ and put them into Y. Now replace $G_i$ with $G^{\prime }_i=G_i\cup \{w,w'\}$ and again divide into two cases. In the case $b_i\geq 2$ , we set $x\in B_i\setminus \{x_1^i\}$ and $S^{\prime }_i=(S_i\setminus \{x\})\cup \{x_1^i,w\}$ . In the case $b_i=1$ , $c_i\geq 2$ , clearly, $D_i=\{x_1^i\}$ , $D^{\prime }_i=\{y_1^i\}$ and $L_i\neq \emptyset $ . Since $L_i\subseteq S_i$ , we set $y\in L_i$ and $S^{\prime }_i=(S_i\setminus {y})\cup \{y_1^i,w\}$ . In both cases, it is not hard to check that $S^{\prime }_i$ is a semitotal forcing set of $G^{\prime }_i$ . Then for $G^{\prime }_i$ , $n^{\prime }_i=n_i+2=b_i+d_i+l_i+3$ and $|S^{\prime }_i|=|S_i|+1=b_i+ l_i+1\leq b_i + d_i(\Delta -2)+1={\kern1pt} b_i -d_i+ d_i(\Delta -1)+1\leq \Delta -1+ d_i(\Delta -1)+1{\kern1pt}={\kern1pt} (d_i+1)(\Delta -1)+1$ , which implies that $d_i+1\geq {(|S^{\prime }_i|-1)}/{(\Delta -1)}$ . Thus, $n^{\prime }_i=b_i+ l_i+d_i+3=|S^{\prime }_i|+d_i+2\geq |S^{\prime }_i|+{(|S^{\prime }_i|-1)}/{(\Delta -1)}+1={(\Delta |S^{\prime }_i|+\Delta -2)}/{(\Delta -1)}> {\Delta |S^{\prime }_i|}/{(\Delta -1)}$ and further $|S^{\prime }_i|<({(\Delta -1)}/{\Delta })n^{\prime }_i$ .

Now return to W. Let $W'=W\setminus (X\cup Y)$ , $D"=D'\setminus Y$ and $S"=L\setminus X$ . Let $R'=W'\cup T(=(D'\setminus Y)\cup (L\setminus X)\cup T)$ and $G_{R'}$ have order $n_{R'}$ . Then $n_{R'}=d"+|S"|+t\geq d"+|S"|$ , where $d"=|D"|$ . Thus, $S=S'\cup S"$ is a semitotal forcing set of G, where some $S_i$ in $S'$ is replaced by $S^{\prime }_i$ . We have $|S"|\leq (\Delta -2)d"\leq (\Delta -2)(n_{R'}-|S"|)= (\Delta -2)n_{R'}-(\Delta -2)|S"|$ . This implies $|S"|\leq ({(\Delta -2)}/{(\Delta -1)})n_{R'}<({(\Delta -1)}/{\Delta })n_{R'}$ . Thus,

$$ \begin{align*} \begin{aligned} |S|=|S'|+|S"| <\frac{\Delta-1}{\Delta}\sum\limits_{i=1}^{r}n_i+\frac{\Delta-1}{\Delta}n_{R'} =\frac{\Delta-1}{\Delta}\bigg(\sum\limits_{i=1}^{r}n_i+n_{R'}\bigg) =\frac{\Delta-1}{\Delta}n. \end{aligned} \end{align*} $$

We now show that the set S is a semitotal forcing set in G. By the construction, S is semitotal. In the first stage of the forcing process, we colour all vertices in $G_i$ for $i\in [r]$ black. As shown earlier, when we apply the colour-change rule to $S_i$ in $G_i$ with the order from small to large, all vertices of $G_i$ turn black.

In the second stage of the forcing process, we colour all vertices of R black. Now we play each of the vertices of D in turn, thereby colouring all vertices in $D'$ black. Finally, all vertices of T can be forced and all vertices of G are coloured black.

Thus, $F_{t2}(G)\leq |S|\leq ({(\Delta -1)}/{\Delta })n$ , as desired. Suppose next that $F_{t2}(G)= ({(\Delta -1)}/{\Delta })n$ . Then S is a minimum semitotal forcing set in G and $|S|= ({(\Delta -1)}/{\Delta })n$ . Recall that by our earlier assumptions, $\Delta \geq 3$ . If $R\neq \emptyset $ , then, as shown above, $|S|< ({(\Delta -1)}/{\Delta })n$ , which is a contradiction. Hence, $R=\emptyset $ , implying that $|S_i|=({(\Delta -1)}/{\Delta })n_i$ . For all $i \in [k]$ , the set $S_i$ must have been constructed as in Subcases 1.1 and 1.2 and equality holds in (4.1) and (4.2), which implies that ( $\Delta =3$ , $G_i=P_3$ ) and ( $b_i=\Delta $ , $d_i=1$ , $l_i=\Delta -2$ ), respectively.

We claim that G is a regular graph. Otherwise, $\delta < \Delta $ and we can choose a weak partition $(A,B,C,A',B',R)$ of V such that $v_1$ is a vertex of minimum degree. Thus, $b_1\neq \Delta $ . Further, $\Delta =3$ and $G_1=P_3$ , where $d(v_1)=1$ . Let $B_1=\{z\}$ . We find that $d(z)=2$ . Now we reselect a weak partition $(A,B,C,A',B',R)$ of V such that $v_1=z$ . Then $d(v_1)=b_i=2<\Delta $ and, by the previous analysis, equality holds in (4.1) and (4.2) for $i=1$ , which is a contradiction. Thus, $\delta =\Delta \geq 3$ .

Now consider $i=1$ . With $S_1$ constructed as in Subcase 1.2, we have $b_1=\Delta $ , $d_1=1$ , $l_1=\Delta -2$ . Then, $d(v_1)=d(x_1^1)=\Delta $ . First, we show that $B_1$ is an independent set. Otherwise, there exist $u,v\in B_1$ different from $x_1$ such that u is adjacent to v. Since $\Delta $ is the maximum degree, there exists $w\in C_1$ such that w is not adjacent to v. Let $S_1'=V(G_1)\setminus \{u,x_1,w\}$ . Then $v\rightarrow u$ and further $v_1\rightarrow x_1^1\rightarrow w$ . Thus, $S_1'$ is a semitotal forcing set of $G_1$ smaller than $S_1$ , and so $(S\setminus S_1)\cup S_1'$ is a semitotal forcing set of G smaller than S, which is a contradiction. Since $\Delta $ is the maximum degree, it is not hard to see that $N(v)=\{v_1\}\cup C_1$ for each $v\in B_1$ . Therefore, $G=K_{\Delta ,\Delta }$ , as desired.

This completes the proof.

Proof. Let G be a connected graph of order $n \geq 3$ with maximum degree $\Delta \geq 2$ . If $G=K_n$ , then $F_{t2}(G)=n-1= ({(\Delta -1)n+1})/{\Delta }$ . Now consider $G\neq K_n$ . If $n=3$ , then $G=P_3$ and $F_{t2}(G)=2= ({(\Delta -1)n+1})/{\Delta }$ , as desired. If $n\geq 4$ , then $F_{t2}(G)\leq {(\Delta -1)n}/{\Delta }<({(\Delta -1)n+1})/{\Delta }$ by Theorem 4.3. Thus, $F_{t2}(G)\leq ({(\Delta -1)n+1})/{\Delta }$ , with equality if and only if $G=K_{n}$ or $G=P_{3}$ .