Number of maximal 2-component independent sets in forests

1.   Introduction

Let $G = (V(G), E(G))$ be a graph. A set $S\subseteq V(G)$ is called an independent set of $G$ if no two vertices of $S$ are adjacent in $G$. A maximal independent set is an independent set that is not a proper subset of any other independent set. Let $k$ be a positive integer. We call $S$ a $k$-component independent set of $G$ if each component of $G[S]$ has order at most $k$. Clearly, the 1-component independent sets are the usual independent sets. A $k$-component independent set is maximal (maximum) if the set cannot be extended to a larger $k$-component independent set (if no $k$-component independent set of $G$ has larger cardinality). A maximal $k$-component independent set of a graph $G$ is denoted briefly by Mk-CIS. We use $t_k(G)$ to denote the number of Mk-CISs of $G$.

In 1986, Wilf ^[12] proved that the maximum number of maximal independent sets for a tree of order $n$ is $2^{\frac{n-1}{2}}$ if $n$ is odd and $2^{\frac{n}{2}-1}+1$ if $n\geq 2$ is even. In 1988, Sagan ^[9] gave a simple graph-theoretical proof and characterized all extremal trees. In 1991, Zito ^[15] determined that the maximum number of maximum independent sets for a tree of order $n$ is $2^{\frac{n-3}{2}}$ if $n > 1$ is odd and $2^{\frac{n-2}{2}}+1$ if $n$ is even, and also characterized all extremal trees. In 1993, Hujter and Tuza ^[4] proved that the maximal number of maximal independent sets in triangle-free graphs is at most $2^{\frac{n}{2}}$ if $n\geq 4$ is even and $5\cdot 2^{\frac{n-5}{2}}$ if $n\geq 5$ is odd, and characterized the extremal graphs. The number of the maximal independent sets on some classes of graphs were also studied in ^[5,6,10,13].

In 2021, Tu, Zhang and Shi ^[11] showed that the maximum number of maximum 2-component independent sets in a tree of order $n$ is $3^{\frac{n}{3}-1}+\frac{n}{3}+1$ if $n\equiv 0$ ($\mod 3$), $3^{\frac{n-1}{3}-1}+1$ if $n\equiv 1$ ($\mod 3$), and $3^{\frac{n-2}{3}-1}$ if $n\equiv 2$ ($\mod 3$), and also characterized the extremal graphs.

In 1981, Yannakakis ^[14] proved that the problem of computing the number of maximum 2-component independent sets for bipartite graphs is NP-complete. The complexity of the problem on some special families of graphs were studied in ^[1,2,7,8].

In this paper, we establish a sharp upper bound for $t_2(G)$ of a forest $G$ of order $n$ and characterize all forests achieving the upper bound.

2.   The main result

Let $G$ be a graph and $v$ a vertex in $G$. The neighborhood $N_G(v)$ is the set of vertices adjacent to $v$ and the closed neighborhood $N_G[v]$ is $N_G(v)\cup \{v\}$. In the sequel, we use $t(G)$ to present $t_2(G)$ for simplicity and $S$ denotes an M2-CIS of a tree $T$ under consideration.

Theorem 2.1. For any forest $F$ of order $n\geq 3$, $t(F)\leq f(n)$, where

with equality if and only if

Lemma 2.2. (Cheng, Wu ^[3])Let $n$ and $k$ be two integers with $n\geq k+1\geq 2$.For any tree $T$ of order $n$, there exists a vertex $v$ such that$T-v$ has $d(v)-1$ components, each of which has order at most $k$, but the sum of theirorder is at least $k$.In particular, every nontrivial tree $T$ has a vertex $v$ such that all its neighbors but one are leaves.

Lemma 2.3. For any positive integer $n\geq 1$,

We define five special trees, denoted by $T_i$ for each $i\in \{1, \dots, 5\}$:

$T_1$ is a tree of order $n$ obtained from $K_{1, 3}$ by subdividing an edge of $K_{1, 3} \; n-4$ times, where $5\leq n\leq 9$.

$T_2$ is obtained from $2P_4\cup P_3$ by adding edges connecting a leaf of each copy of $P_4$ to a leaf $x$ of $P_3$.

$T_3$ is obtained from $(K_{1, 3}\cup P_4)\cup P_3$ by adding edges connecting a leaf of $K_{1, 3}$ and $P_4$ to a leaf $x$ of $P_3$.

$T_4$ is obtained from $aK_{1, 3}\cup P_3$ by adding edges connecting a leaf of each copy of $K_{1, 3}$ to a leaf $x$ of $P_3$ for an integer $a\geq 2$.

$T_5$ is obtained from $bK_{1, 3}$ by adding edges connecting a leaf of each copy of $K_{1, 3}$ to a fixed vertex $x$ for an integer $b\geq 2$, as shown in Figure 1.

Lemma 2.4. $t(T_i)\leq t(F_n)$ for each $i\in \{1, \dots, 5\}$.

Proof. By a straightforward calculation,

Obviously, $|V(T_2)| = |V(T_3)| = 11$, $t(T_2) = 28 < 4^2\cdot3 = t(2K_{1, 3}\cup P_3) = t(F_{11})$, and $t(T_3) = 31 < 4^2\cdot3 = t(2K_{1, 3}\cup P_3) = t(F_{11})$.

Note that $|V(T_4)| = 4a+3$. Observe that for an M2-CIS $S$ of $T_4$, either $x\notin S$ or $x\in S$ with $d_{T[S]}(x)\leq 1$. Let us define $t^0_x = |\{S: d_{T[S]}(x) = 0\}| = 2^a$, $t^1_x = |\{S: d_{T[S]}(x) = 1\}| = (a+3)\cdot3^{a-1}$, $t_{\bar{x}} = |\{S: x\notin S\}| = 4^a$. Thus, $t(T_4) = t^0_x+t^1_x+t_{\bar{x}} = 4^a+(a+3)\cdot3^{a-1}+2^a.$ We consider three cases in terms of the modularity of $a$ ($\mod 3$).

If $a = 3s$, $s\geq 1$, then $|V(T_4)| = 12s+3$ and $t(F_{12s+3}) = 3^{4s+1}$. Moreover, since $4^{3s}\leq3^{4s}$ and $(s+1)\cdot3^{3s}+2^{3s}\leq 2\cdot3^{4s}$ for any $s\geq 1$, it follows that for any $s\geq 1$,

If $a = 3s+1$, $s\geq1$, then $|V(T_4)| = 12s+7$ and $t(F_{12s+7}) = 4\cdot3^{4s+1}$. Moreover, since $4^{3s+1}\leq 4\cdot3^{4s}$ and $(3s+4)\cdot3^{3s}+2^{3s+1}\leq 8\cdot3^{4s}$ for any $s\geq 1$, it follows that for any $s\geq 1$,

If $a = 3s+2$, $s\geq 0$, then $|V(T_4)| = 12s+11$ and $t(F_{12s+11}) = 4^2\cdot3^{4s+1}$. Moreover, since $4^{3s+2}\leq 4^2\cdot3^{4s}$ and $(3s+5)\cdot3^{3s+1}+2^{3s+2}\leq 32\cdot3^{4s}$ for any $s\geq 0$, it follows that for any $s\geq 0$,

Note that $|V(T_5)| = 4b+1$ and $t(T_5) = 4^b+b\cdot3^{b-1}-b\cdot2^{b-1}$. We consider three cases in terms of the modularity of $b$ ($\mod 3$).

If $b = 3s$, $s\geq 1$, then $|V(T_5)| = 12s+1$ and $t(F_{12s+1}) = 4\cdot3^{4s-1}$. Moreover, since $4^{3s}\leq 3^{4s}$ and $s\cdot3^{3s}\leq3^{4s-1}$ for any $s\geq1$, it follows that for any $s\geq 1$,

If $b = 3s+1$, $s\geq1$, then $|V(T_5)| = 12s+5$ and $t(F_{12s+5}) = 4^2\cdot3^{4s-1}$. Moreover, since $4^{3s+1}\leq 4\cdot3^{4s}$ and $(3s+1)\cdot3^{3s}\leq 4\cdot3^{4s-1}$ for any $s\geq 1$, it follows that for any $s\geq 1$,

If $b = 3s+2$, $s\geq0$, then $|V(T_5)| = 12s+9$ and $t(F_{12s+9}) = 3^{4s+3}$. Moreover, since $4^{3s+2}\leq 4^2\cdot3^{4s}$ and $(3s+2)\cdot3^{3s+1}\leq 11\cdot3^{4s}$ for any $s\geq 0$, it follows that for any $s\geq 0$,

3.   The proof of Theorem 2.1

In this section, we give the proof of Theorem 2.1.

Proof. Let $F$ be a forest of order $n$. It is straightforward to check that the result is true if $n\leq 5$. We proceed with the induction on the order $n$ of $F$. If $F\cong K_{1, n-1}$, then by Lemma 2.3, the result trivially holds. Next we assume that $F$ is not a star. By Lemma 2.2, for a tree $T$, there exists a vertex $x$ with $d(x)-1$ neighbors being leaves. Let $N(x) = \{x_1, \ldots, x_{d(x)-1}, y\}$, where $y$ is the neighbor of $x$ which is not a leaf of $T$, as shown in Figure 2.

Claim 1. If $d(x)\geq 6$, then $t(T)\leq t(F_n)$.

Proof. Let $T_x$ and $T_y$ be two components of $T-xy$ containing $x$ and $y$ respectively. Then $|V(T_x)| = d(x)$. Observe that for an M2-CIS $S$ of $T$, either $x\notin S$ or $x\in S$ with $d_{T[S]}(x) = 1$. Let us define

$t_{\bar{x}} = |\{S: x\notin S\}|$,

$t^1_x = |\{S: d_{T[S]}(x) = 1\}|$

 $= |\{S: d_{T[S]}(x) = 1, \{x, y\}\subseteq S\}|+|\{S: d_{T[S]}(x) = 1, \{x, x_i\}\subseteq S,$

  $i\in \{1, \dots, d(x)-1\}\}|$.

Thus, $t(T) = t_{\bar{x}}+t^1_x.$ Since $t_{\bar{x}} = t(T_y)$ and $t^1_x\leq d(x)\cdot t(T_y)$, we have

Let $V(T'_x) = V(T_x)$. We consider three cases in terms of the modularity of $d(x)$ ($\mod 3$).

Case 1. $d(x) = 3s$, $s\geq 2$

Let $T'_x = s P_3$. Then $t(T'_x) = 3^s$. By (3.1), it follows that for any $s\geq 2$,

By the induction hypothesis, $t(T_y)\leq t(F_{n-d(x)})$. Hence, $t(T)\leq t(F_n)$.

Case 2. $d(x) = 3s+1$, $s\geq 2$

Let $T'_x = (s-1)P_3\cup K_{1, 3}$. Then $t(T'_x) = 4\cdot3^{s-1}$. By (3.1), it follows that for any $s\geq 2$,

By the induction hypothesis, $t(T_y)\leq t(F_{n-d(x)})$. Hence, $t(T)\leq t(F_n)$.

Case 3. $d(x) = 3s+2$, $s\geq 2$

Let $T'_x = (s-2)P_3 \cup 2 K_{1, 3}$. Then $t(T'_x) = 4^2\cdot3^{s-2}$. By (3.1), it follows that for any $s\geq 2$,

By the induction hypothesis, $t(T_y)\leq t(F_{n-d(x)})$. Hence, $t(T)\leq t(F_n)$.

Claim 2. If $d(x) = 4$ or 5, then $t(T)\leq t(F_n)$.

Proof. The meanings of notations here are same as those adopted in Claim 1. Let $F_1 = T-(N[x]\setminus \{y\})$, $F_2 = T-N(x)-N(y)$ and $F_3 = T-N[x]$. Combining these observations with the definition of $F_i$, we get that $t_{\bar{x}} = t(F_1)$, $t^1_x = t(F_2)+(d(x)-1)\cdot t(F_3)$. Since $t(T) = t_{\bar{x}}+t^1_x$, we have

Let $n_i$ be the order of $F_i$ for each $i\in\{1, 2, 3\}$. Then $n_1 = n-d(x)$, $n_2 = n-d(x)-d(y)$ and $n_3 = n-d(x)-1$. We consider three cases in terms of the modularity of $n$ ($\mod 3$).

Case 1. $n = 3s$, $s\geq 2$

Subcase 1.1. $d(y) = 3l$, $l\geq 1$

If $d(x) = 4$, then $n_1 = 3(s-2)+2$, $n_2 = 3(s-l-2)+2$ and $n_3 = 3(s-2)+1$. By the induction hypothesis, $t(F_1)\leq 4^2\cdot3^{s-4}$, $t(F_2)\leq 4^2\cdot3^{s-l-4}$ and $t(F_3)\leq 4\cdot3^{s-3}$. Moreover, since $\frac{4^2}{3^l}+52\leq 3^4$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

If $d(x) = 5$, then $n_1 = 3(s-2)+1$, $n_2 = 3(s-l-2)+1$ and $n_3 = 3(s-2)$. By the induction hypothesis, $t(F_1)\leq 4\cdot3^{s-3}$, $t(F_2)\leq 4\cdot3^{s-l-3}$ and $t(F_3)\leq 3^{s-2}$. Moreover, since $\frac{4}{3^l}+16\leq 3^3$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 1.2. $d(y) = 3l+1$, $l\geq 1$

If $d(x) = 4$, then $n_2 = 3(s-l-2)+1$. By the induction hypothesis, $t(F_2)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{12}{3^l}+52\leq 3^4$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

If $d(x) = 5$, then $n_2 = 3(s-l-2)$. By the induction hypothesis, $t(F_2)\leq 3^{s-l-2}$. Moreover, since $\frac{3}{3^l}+16\leq 3^3$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 1.3. $d(y) = 3l+2$, $l\geq 0$

If $d(x) = 4$, then $n_2 = 3(s-l-2)$. By the induction hypothesis, $t(F_2)\leq 3^{s-l-2}$. Moreover, since $\frac{9}{3^l}+52\leq 3^4$ for any $l\geq 0$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 0$,

If $d(x) = 5$, then $n_2 = 3(s-l-3)+2$. By the induction hypothesis, $t(F_2)\leq 4^2\cdot3^{s-l-5}$. Moreover, since $\frac{4^2}{3^l}+144\leq 3^5$ for any $l\geq 0$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 0$,

Case 2. $n = 3s+1$, $s\geq 2$

Subcase 2.1. $d(y) = 3l, l\geq 1$

If $d(x) = 4$, then $n_1 = 3(s-1)$, $n_2 = 3(s-l-1)$ and $n_3 = 3(s-2)+2$. By the induction hypothesis, $t(F_1)\leq 3^{s-1}$, $t(F_2)\leq 3^{s-l-1}$ and $t(F_3)\leq 4^2\cdot3^{s-4}$. Moreover, since $\frac{9}{3^l}+25\leq 4\cdot3^2$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

If $d(x) = 5$, then $n_1 = 3(s-2)+2$, $n_2 = 3(s-l-2)+2$ and $n_3 = 3(s-2)+1$. By the induction hypothesis, $t(F_1)\leq 4^2\cdot3^{s-4}$, $t(F_2)\leq 4^2\cdot3^{s-l-4}$ and $t(F_3)\leq 4\cdot3^{s-3}$. Moreover, since $\frac{4^2}{3^l}+64\leq 4\cdot3^3$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.2. $d(y) = 3l+1$, $l\geq 1$

If $d(x) = 4$, then $n_2 = 3(s-l-2)+2$. By the induction hypothesis, $t(F_2)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{4^2}{3^{l+1}}+25\leq 4\cdot3^2$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

If $d(x) = 5$, then $n_2 = 3(s-l-2)+1$. By the induction hypothesis, $t(F_2)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{12}{3^{l}}+64\leq 4\cdot3^3$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.3. $d(y) = 3l+2$, $l\geq 0$

If $d(x) = 4$, then $n_2 = 3(s-l-2)+1$. By the induction hypothesis, $t(F_2)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{4}{3^l}+25\leq 4\cdot3^2$ for any $l\geq 0$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 0$,

If $d(x) = 5$, then $n_2 = 3(s-l-2)$. By the induction hypothesis, $t(F_2)\leq 3^{s-l-2}$. Moreover, since $\frac{3^2}{3^l}+64\leq 4\cdot3^2$ for any $l\geq 0$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 0$,

Case 3. $n = 3s+2$, $s\geq 2$

Subcase 3.1. $d(y) = 3l, l\geq 1$

If $d(x) = 4$, then $n_1 = 3(s-1)+1$, $n_2 = 3(s-l-1)+1$ and $n_3 = 3(s-1)$. By the induction hypothesis, $t(F_1)\leq 4\cdot3^{s-2}$, $t(F_2)\leq 4\cdot3^{s-l-2}$ and $t(F_3)\leq 3^{s-1}$. Moreover, since $\frac{4}{3^l}+13\leq 4^2$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

If $d(x) = 5$, then $n_1 = 3(s-1)$, $n_2 = 3(s-l-1)$ and $n_3 = 3(s-2)+2$. By the induction hypothesis, $t(F_1)\leq 3^{s-1}$, $t(F_2)\leq 3^{s-l-1}$ and $t(F_3)\leq 4^2\cdot3^{s-4}$. Moreover, since $\frac{3^3}{3^l}+91\leq 4^2\cdot3^2$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 3.2. $d(y) = 3l+1$, $l\geq 1$

If $d(x) = 4$, then $n_2 = 3(s-l-1)$. By the induction hypothesis, $t(F_2)\leq 3^{s-l-1}$. Moreover, since $\frac{3}{3^l}+13\leq 4^2$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

If $d(x) = 5$, then $n_2 = 3(s-l-2)+2$. By the induction hypothesis, $t(F_2)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{4^2}{3^l}+91\leq 4^2\cdot3^2$ for any $l\geq 1$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 3.3. $d(y) = 3l+2$, $l\geq 0$

If $d(x) = 4$, then $n_2 = 3(s-l-2)+2$. By the induction hypothesis, $t(F_2)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{4^2}{3^{l+2}}+13\leq 4^2$ for any $l\geq 0$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 0$,

If $d(x) = 5$, then $n_2 = 3(s-l-2)+1$. By the induction hypothesis, $t(F_2)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{12}{3^{l}}+91\leq 4^2\cdot3^2$ for any $l\geq 0$, by (3.2), it follows that for any $s\geq 2$ and $l\geq 0$,

Claim 3. $t(T)\leq t(F_n)$ if one of the following conditions holds:

(1) $n\geq 6$, $n\equiv 0$ or 1 $(\mod 3)$, $d(x) = 3$;

(2) $n\geq 8$, $n\equiv 2 \; (\mod 3)$, $d(x) = 3$, $d(y)\geq 3$, where $y\in N(x)$.

Proof. The meanings of notations here are same as those adopted in Claims 1 and 2. By (3.2), we have

Let $n_i$ be the order of $F_i$ for each $i\in\{1, 2, 3\}$. We consider three cases in terms of the modularity of $n$ ($\mod 3$).

Case 1. $n = 3s$, $s\geq 2$.

$n_1 = 3(s-1)$, $n_3 = 3(s-2)+2$. By the induction hypothesis, $t(F_1)\leq 3^{s-1}$ and $t(F_3)\leq 4^2\cdot3^{s-4}$.

Subcase 1.1. $d(y) = 3l$, $l\geq 1$

Since $n_2 = 3(s-l-1)$, by the induction hypothesis, $t(F_2)\leq 3^{s-l-1}$. Moreover, since $\frac{3^3}{3^l}+59\leq 3^4$ for any $l\geq 1$, by (3.3), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 1.2. $d(y) = 3l+1$, $l\geq 1$

Since $n_2 = 3(s-l-2)+2$, by the induction hypothesis, $t(F_2)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{4^2}{3^l}+59\leq 3^4$ for any $l\geq 1$, by (3.3), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 1.3. $d(y) = 3l+2$, $l\geq 0$

Since $n_2 = 3(s-l-2)+1$, by the induction hypothesis, $t(F_2)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{12}{3^l}+59\leq 3^4$ for any $l\geq 0$, by (3.3), it follows that for any $s\geq 2$ and $l\geq 0$,

Case 2. $n = 3s+1$, $s\geq 2$

By the definition of $n_i$, $n_1 = 3(s-1)+1$, $n_3 = 3(s-1)$. By the induction hypothesis, $t(F_1)\leq 4\cdot3^{s-2}$ and $t(F_3)\leq 3^{s-1}$.

Subcase 2.1. $d(y) = 3l$, $l\geq 1$

Since $n_2 = 3(s-l-1)+1$, by the induction hypothesis, $t(F_2)\leq 4\cdot3^{s-l-2}$. Moreover, since $\frac{4}{3^l}+10\leq 4\cdot3$ for any $l\geq 1$, by (3.3), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.2. $d(y) = 3l+1$, $l\geq 1$

Since $n_2 = 3(s-l-1)$, by the induction hypothesis, $t(F_2)\leq 3^{s-l-1}$. Moreover, since $\frac{3}{3^l}+10\leq 4\cdot3$ for any $l\geq 1$, by (3.3), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.3. $d(y) = 3l+2$, $l\geq 0$

Since $n_2 = 3(s-l-2)+2$, by the induction hypothesis, $t(F_2)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{4^2}{3^l}+90\leq 4\cdot3^3$ for any $l\geq 0$, by (3.3), it follows that for any $s\geq 2$ and $l\geq 0$,

Case 3. $n = 3s+2$, $s\geq 2$

By the definition of $n_i$, $n_1 = 3(s-1)+2$, $n_3 = 3(s-1)+1$. By the induction hypothesis, $t(F_1)\leq 4^2\cdot3^{s-3}$ and $t(F_3)\leq 4\cdot3^{s-2}$.

Subcase 3.1. $d(y) = 3l$, $l\geq 1$

Since $n_2 = 3(s-l-1)+2$, by the induction hypothesis, $t(F_2)\leq 4^2\cdot3^{s-l-3}$. Moreover, since $\frac{4^2}{3^l}+40\leq 4^2\cdot3$ for any $l\geq 1$, by (3.3), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 3.2. $d(y) = 3l+1$, $l\geq1$

Since $n_2 = 3(s-l-1)+1$, by the induction hypothesis, $t(F_2)\leq 4\cdot3^{s-l-2}$. Moreover, since $\frac{12}{3^l}+40\leq 4^2\cdot3$ for any $l\geq 1$, by (3.3), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 3.3. $d(y) = 3l+2$, $l\geq 1$

Since $n_2 = 3(s-l-1)$, by the induction hypothesis, $t(F_2)\leq 3^{s-l-1}$. Moreover, since $\frac{3^2}{3^l}+40\leq 4^2\cdot3$ for any $l\geq 1$, by (3.3), it follows that for any $s\geq 2$ and $l\geq 1$,

In view of Claim 3, we consider the case that $d(y) = 2$ and $n = 3s+2$ where $s\geq2$.

Claim 4. Assume that $d(y) = 2$ for the remaining neighbor $y$ of $x$ and $d(z)\geq 1$ for the neighbor of $y$ other than $x$, as shown in Figure 3. If $T-z$ has an isolated vertex or an isolated edge, then $t(T)\leq t(F_n)$.

Proof. Let $T_x$ and $T_y$ be two components of $T-xy$ containing $x$ and $y$ respectively.

Case 1. $T-z$ has exactly an isolated vertex.

By Lemma 2.4, we distinguish two subcases in terms of $d(z)\geq 3$.

Subcse 1.1. $d(z) = 3$

Observe that for an M2-CIS $S'$ of $T_y$, either $y\notin S'$ or $y\in S'$ with $d_{T[S']}(y)\leq 1$. Let us define $\tilde{t}^0_y = |\{S': d_{T[S']}(y) = 0\}|$, $\tilde{t}^1_y = |\{S': d_{T[S']}(y) = 1\}|$, $\tilde{t}_{\bar{y}} = |\{S': y\notin S'\}|$. Thus, $t(T_y) = \tilde{t}^0_y+\tilde{t}^1_y+\tilde{t}_{\bar{y}}.$

Observe that for an M2-CIS $S$ of $T$, either $y\notin S$ or $y\in S$ with $d_{T[S]}(y)\leq1$. Let

$t^0_y = |\{S: d_{T[S]}(y) = 0\}| = \tilde{t}^0_y$,

$t^1_y = |\{S: d_{T[S]}(y) = 1\}|$

 $= |\{S: d_{T[S]}(y) = 1, \{x, y\}\subseteq S\}|+|\{S: d_{T[S]}(y) = 1, \{y, z\}\subseteq S\}|$

 $= \tilde{t}^0_y+\tilde{t}^1_y$.

$t_{\bar{y}} = |\{S: y\notin S\}| = |\{S: y\notin S, x\in S\}|+|\{S: y\notin S, x\notin S\}|$

 $\leq(\tilde{t}^0_y+2\tilde{t}^1_y+2\tilde{t}_{\bar{y}})+\tilde{t}_{\bar{y}} = \tilde{t}^0_y+2\tilde{t}^1_y+3\tilde{t}_{\bar{y}}$.

Clearly, $t(T) = t^0_y+t^1_y+t_{\bar{y}}\leq 3\tilde{t}^0_y+3\tilde{t}^1_y+3\tilde{t}_{\bar{y}}$. Since $t(T_y) = \tilde{t}^0_y+\tilde{t}^1_y+\tilde{t}_{\bar{y}}$, $t(T)\leq 3t(T_y) = t(T_x)\cdot t(T_y)$. By the induction hypothesis, $t(T_y)\leq t(F_{n-3})$. Hence, $t(T)\leq t(T_x)\cdot t(F_{n-3})\leq t(F_n)$.

Subcase 1.2. $d(z)\geq 4$

Let $T-yz = T_y\cup T_z$ where $z\in T_z$. Observe that for an M2-CIS $S'$ of $T_z$, either $z\notin S'$ or $z\in S'$ with $d_{T[S']}(z) = 1$. Let us define $t_{\bar{z}} = |\{S': z\notin S'\}|$ and $t^1_z = |\{S': d_{T[S']}(z) = 1\}|$. Thus, $t(T_z) = t_{\bar{z}}+t^1_z.$

The meanings of notations here are same as those adopted in Subcase 1.1. Note that $t^0_y+t^1_y\leq t^1_z+2t_{\bar{z}}$ and $t_{\bar{y}} = 2t(T_z)+t^1_z$. Thus, $t(T)\leq 2t(T_z)+2(t^1_z+t_{\bar{z}})$. Since $t(T_z) = t_{\bar{z}}+t^1_z$, $t(T)\leq 4t(T_z) = t(T_y)\cdot t(T_z)$. By the induction hypothesis, $t(T_z)\leq t(F_{n-4})$. Hence, $t(T)\leq t(T_y)\cdot t(F_{n-4})\leq t(F_n)$.

Case 2. $T-z$ has two isolated vertices.

The meanings of notations here are same as those adopted in Subcases 1.1 and 1.2. Note that $t(T_z) = t^1_z+t_{\bar{z}}$, $t^0_y = t_{\bar{z}}$, $t^1_y\leq t_{\bar{z}}+t^1_z$, $t_{\bar{y}} = 2t(T_z)+t^1_z$. Thus, $t(T)\leq 2t(T_z)+2(t^1_z+t_{\bar{z}}) = 4t(T_z) = t(T_y)\cdot t(T_z)$. By the induction hypothesis, $t(T_z)\leq t(F_{n-4})$. Hence, $t(T)\leq t(T_y)\cdot t(F_{n-4})\leq t(F_n)$.

Case 3. $T-z$ has an isolated edge.

Note that $t^1_z+t_{\bar{z}}\leq t(T_z)$. By a similar argument as in the proof of Case 2, we show that $t(T)\leq t(F_n)$.

In view of Claim 4, we consider the case that $d(z) = 2$.

Claim 5. Assume that there exists a path $P: = xyzw$ in $T$ with $d(x) = 3, d(y) = d(z) = 2$, as shown in Figure 4. We have $t(T)\leq t(F_n)$ if one of the following conditions holds:

(1) $T-w$ has an isolated vertex or an isolated edge;

(2) $T-w$ has no isolated vertex or isolated edge, where $d(w)\neq2$.

Proof. Let $N(w) = \{w_1, \dots, w_{d(w)-1}, z\}$. We consider two cases in the following.

Case 1. $T-w$ has an isolated vertex or an isolated edge.

Subcase 1.1. $T-w$ has an isolated vertex.

Let $T-yz = T_y\cup T_z$ where $z\in T_z$. Observe that for an M2-CIS $S'$ of $T_z$, either $z\notin S'$ or $z\in S'$ with $d_{T[S']}(z)\leq 1$. Let us define $\tilde{t}^0_z = |\{S': d_{T[S']}(z) = 0\}|$, $\tilde{t}_{\bar{z}} = |\{S': z\notin S'\}|$, $\tilde{t}^1_z = |\{S': d_{T[S']}(z) = 1\}|$. Thus, $t(T_z) = \tilde{t}^0_z+\tilde{t}^1_z+\tilde{t}_{\bar{z}}.$

Observe that for an M2-CIS $S$ of $T$, either $z\notin S$ or $z\in S$ with $d_{T[S]}(z)\leq 1$. Let

$t^0_z = |\{S: d_{T[S]}(z) = 0\}| = 2\tilde{t}^0_z$,

$t^1_z = |\{S: d_{T[S]}(z) = 1\}|$

 $= |\{S: d_{T[S]}(z) = 1, \{y, z\}\subseteq S\}|+|\{S: d_{T[S]}(z) = 1, \{z, w\}\subseteq S\}|$

 $= \tilde{t}^0_z+3\tilde{t}^1_z$,

$t_{\bar{z}} = |\{S: z\notin S\}|$

 $= |\{S: z\notin S, y\in S, d_{T[S]}(y) = 0\}|+|\{S: z\notin S, y\in S, d_{T[S]}(y) = 1\}|$

  $+|\{S: z\notin S, y\notin S\}|$

 $= \tilde{t}_{\bar{z}}+(|\{S: z\notin S, y\in S, d_{T[S]}(y) = 1, w\notin S\}|$

  $+|\{S: z\notin S, y\in S, d_{T[S]}(y) = 1, w\in S\}|)+2\tilde{t}_{\bar{z}}$

 $\leq3\tilde{t}_{\bar{z}}+(\tilde{t}^0_z+\tilde{t}_{\bar{z}}) = \tilde{t}^0_z+4\tilde{t}_{\bar{z}}$.

Obviously, $t(T) = t^0_z+t^1_z+t_{\bar{z}}\leq 4\tilde{t}^0_z+3\tilde{t}^1_z+4\tilde{t}_{\bar{z}}$. Since $t(T_z) = \tilde{t}^0_z+\tilde{t}^1_z+\tilde{t}_{\bar{z}}$, $t(T)\leq 4t(T_z) = t(T_y)\cdot t(T_z)$. By the induction hypothesis, $t(T_z)\leq t(F_{n-4})$. Hence, $t(T)\leq t(T_y)\cdot t(F_{n-4})\leq t(F_n)$.

Subcase 1.2. $T-w$ has an isolated edge.

By Lemma 2.4, $d(w)\geq3$. Let $T-zw = T_z\cup T_w$ where $w\in T_w$ and $T'_z = K_{1, 4}$ where $V(T'_z) = V(T_z)$. Then $t(T'_z) = 5$. Observe that for an M2-CIS $S'$ of $T_w$, either $w\notin S'$ or $w\in S'$ with $d_{T[S']}(w)\leq 1$. Let us define $t^0_w = |\{S': d_{T[S']}(w) = 0\}|$, $t_{\bar{w}} = |\{S': w\notin S'\}|$, $t^1_w = |\{S': d_{T[S']}(w) = 1\}|$. Thus, $t(T_w) = t^0_w+t^1_w+t_{\bar{w}}.$

The meanings of notations here are same as those adopted in Subcase 1.1. Note that $t^0_z = 2t_{\bar{w}}$, $t^1_z\leq 2t^0_w+t^1_w+2t_{\bar{w}}$ and $t_{\bar{z}} = t(T_w)+t^0_w+3t^1_w$.

We obtain that $t(T) = t^0_z+t^1_z+t_{\bar{z}}\leq t(T_w)+3t^0_w+4t^1_w+4t_{\bar{w}}$. Since $t(T_w) = t^0_w+t^1_w+t_{\bar{w}}$, $t(T)\leq5t(T_w) = t(T'_z)\cdot t(T_w)$. By the induction hypothesis, $t(T_w)\leq t(F_{n-5})$. Hence, $t(T)\leq t(T'_z)\cdot t(F_{n-5})\leq t(F_n)$.

Case 2. $T-w$ has no isolated vertex or isolated edge, where $d(w)\neq2$.

The meanings of notations here are same as those adopted in Subcase 1.1. Let $F_1 = T-(N[x]\cup\{z\})$, $F_2 = T-N[x]-V(P)$, $F_3 = T-N[x]-V(P)-N(w)$ and $F_4 = T-N[x]-V(P)-N(w)-N(w_i)$. Combining these observations with the definition of $F_i$, we get that $t^0_z = 2t(F_2)$, $t^1_z = t(F_2)+3t(F_3)$, $t_{\bar{z}} = t(F_1)+t(F_3)+3(d(w)-1)\cdot t(F_4)$. Since $t(T) = t^0_z+t^1_z+t_{\bar{z}}$, we have

Let $n_i$ be the order of $F_i$ for each $i\in\{1, 2, 3, 4\}$. Then $n_1 = 3(s-1)$, $n_2 = 3(s-2)+2$. By the induction hypothesis, $t(F_1)\leq 3^{s-1}$ and $t(F_2)\leq 4^2\cdot3^{s-4}$. We consider three cases in terms of the modularity of $d(w)$ ($\mod 3$).

Subcase 2.1. $d(w) = 3l, l\geq 1$

Since $n_3 = 3(s-l-1)$, $n_4\leq 3(s-l-2)+2$, by the induction hypothesis, $t(F_3)\leq 3^{s-l-1}$ and $t(F_4)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{48l+20}{3^l}+25\leq 4^2\cdot3$ for any $l\geq 1$, by (3.4), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.2. $d(w) = 3l+1, l\geq 1$

Since $n_3 = 3(s-l-2)+2$, $n_4\leq3(s-l-2)+1$, by the induction hypothesis, $t(F_3)\leq 4^2\cdot3^{s-l-4}$ and $t(F_4)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{108l+64}{3^l}+75\leq 4^2\cdot3^2$ for any $l\geq1$, by (3.4), it follows that for any $s\geq 2$ and $l\geq1$,

Subcase 2.3. $d(w) = 3l+2, l\geq 1$

Since $n_3 = 3(s-l-2)+1$, $n_4\leq3(s-l-2)$, by the induction hypothesis, $t(F_3)\leq 4\cdot3^{s-l-3}$ and $t(F_4)\leq 3^{s-l-2}$. Moreover, since $\frac{27l+25}{3^l}+25\leq 4^2\cdot3$ for any $l\geq 1$, by (3.4), it follows that for any $s\geq 2$ and $l\geq 1$,

In view of Claim 5, we proceed to consider the case that $d(w) = 2$.

Claim 6. Assume that there exists a path $P: = xyzwu$ in $T$ with $d(x) = 3, d(y) = d(z) = d(w) = 2$, as shown in Figure 5. We have $t(T)\leq t(F_n)$ if one of the following conditions holds:

(1) $T-u$ has an isolated vertex or an isolated edge;

(2) $T-u$ has no isolated vertex or isolated edge, where $d(u)\neq2$.

Proof. Let $T-wu = T_w\cup T_u$ where $u\in T_u$ and $N(u) = \{u_1, \dots, u_{d(u)-1}, w\}$.

Case 1. $T-u$ has an isolated vertex or an isolated edge.

Subcase 1.1. $T-u$ has an isolated vertex.

By Lemma 2.4, $d(u)\geq3$. Let $T'_w = 2P_3$ where $V(T'_w) = V(T_w)$. Then $t(T'_w) = 9$. Observe that for an M2-CIS $S'$ of $T_u$, either $u\notin S'$ or $u\in S'$ with $d_{T[S']}(u) = 1$. Let us define $t^1_u = |\{S': d_{T[S']}(u) = 1\}|$, $t_{\bar{u}} = |\{S': u\notin S'\}|$. Thus, $t(T_u) = t^1_u+t_{\bar{u}}.$

Observe that for an M2-CIS $S$ of $T$, either $w\notin S$ or $w\in S$ with $d_{T[S]}(w)\leq 1$. Let

$t^0_w = |\{S: d_{T[S]}(w) = 0\}|\leq4t_{\bar{u}}$,

$t^1_w = |\{S: d_{T[S]}(w) = 1\}|$

 $= |\{S: d_{T[S]}(w) = 1, \{w, u\}\subseteq S\}|+|\{S: d_{T[S]}(w) = 1, \{w, z\}\subseteq S\}|$

 $\leq 4t^1_u+(t^1_u+4t_{\bar{u}}) = 5t^1_u+4t_{\bar{u}}$.

$t_{\bar{w}} = |\{S: w\notin S\}|$

 $= |\{S: w\notin S, z\in S, d_{T[S]}(z) = 0\}|+|\{S: w\notin S, z\in S, d_{T[S]}(z) = 1\}|$

  $+|\{S: w\notin S, z\notin S\}|$

 $= 2t^1_u+t(T_u)+t^1_u = 3t^1_u+t(T_u)$.

Clearly, $t(T) = t^0_w+t^1_w+t_{\bar{w}}\leq t(T_u)+8(t^1_u+t_{\bar{u}})$. Since $t(T_u) = t^1_u+t_{\bar{u}}$, $t(T)\leq 9t(T_u) = t(T'_w)\cdot t(T_u)$. By the induction hypothesis, $t(T_u)\leq t(F_{n-6})$. Hence, $t(T)\leq t(T'_w)\cdot t(F_{n-6})\leq t(F_n)$.

Subcase 1.2. $T-u$ has an isolated edge.

The meanings of notations here are same as those adopted in Subcase 1.1, with exception that adding the definition of $t^0_u$. More precisely, let $t^0_u = |\{S': d_{T[S']}(u) = 0\}|$. Then $t(T_u) = t^0_u+t^1_u+t_{\bar{u}}$.

Note that $t^0_w = 2t_{\bar{u}}$, $t^1_w\leq4t^1_u+3t_{\bar{u}}$ and $t_{\bar{w}}\leq2t^0_u+3t^1_u+t(T_u)$. Thus, $t(T) = t^0_w+t^1_w+t_{\bar{w}}\leq t(T_u)+2t^0_u+7t^1_u+5t_{\bar{u}}$. Moreover, $t(T_u) = t^0_u+t^1_u+t_{\bar{u}}$, $t(T)\leq 8t(T_u) < 9t(T_u) = t(T'_w)\cdot t(T_u)$. By the induction hypothesis, $t(T_u)\leq t(F_{n-6})$. Hence, $t(T)\leq t(T'_w)\cdot t(F_{n-6})\leq t(F_n)$.

Case 2. $T-u$ has no isolated vertex or isolated edge, where $d(u)\neq2$.

The meanings of notations here are same as those adopted in Subcase 1.1. Let $F_1 = T-N(x)-V(P)$, $F_2 = T-N(x)-(V(P)\backslash \{u\})$, $F_3 = T-N(x)-V(P)-N(u)$ and $F_4 = T-N(x)-V(P)-N(u)-N(u_i)$. Combining these observations with the definition of $F_i$, we get that $t^0_w = 2t(F_1)$, $t^1_w = 3t(F_1)+4t(F_3)$, $t_{\bar{w}} = t(F_2)+2t(F_3)+3(d(u)-1)\cdot t(F_4)$. Since $t(T) = t^0_w+t^1_w+t_{\bar{w}}$, we have

Let $n_i$ be the order of $F_i$ for $i\in\{1, 2, 3, 4\}$. Then $n_1 = 3(s-2)+1$ and $n_2 = 3(s-2)+2$. By the induction hypothesis, $t(F_1)\leq 4\cdot3^{s-3}$ and $t(F_2)\leq 4^2\cdot3^{s-4}$. Now we consider three subcases in terms of $d(u)$ ($\mod 3$).

Subcase 2.1. $d(u) = 3l$, $l\geq 1$

By the definition of $n_i$, $n_3 = 3(s-l-2)+2$ and $n_4\leq 3(s-l-2)+1$. By the induction hypothesis, $t(F_3)\leq 4^2\cdot3^{s-l-4}$ and $t(F_4)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{108l+60}{3^l}+76\leq 4^2\cdot3^2$ for any $l\geq 1$, by (3.5), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.2. $d(u) = 3l+1, l\geq 1$

By the definition of $n_i$, $n_3 = 3(s-l-2)+1$ and $n_4 = 3(s-l-2)$. By the induction hypothesis, $t(F_3)\leq 4\cdot3^{s-l-3}$ and $t(F_4)\leq 3^{s-l-2}$. Moreover, since $\frac{81l+72}{3^l}+76\leq 4^2\cdot3^2$ for any $l\geq 1$, by (3.5), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.3. $d(u) = 3l+2, l\geq 1$

By the definition of $n_i$, $n_3 = 3(s-l-2)$ and $n_4 = 3(s-l-3)+2$. By the induction hypothesis, $t(F_3)\leq 3^{s-l-2}$ and $t(F_4)\leq 4^2\cdot3^{s-l-5}$. Moreover, since $\frac{48l+70}{3^l}+76\leq 4^2\cdot3^2$ for any $l\geq 1$, by (3.5), it follows that for any $s\geq 2$ and $l\geq 1$,

In view of Claim 6, we proceed to consider the case that $d(u) = 2$.

Claim 7. Assume that there exists a path $P: = xyzwuq$ in $T$ with $d(x) = 3, d(y) = d(z) = d(w) = d(u) = 2$, as shown in Figure 6. We have $t(T)\leq t(F_n)$.

Proof. Let $T-uq = T_u\cup T_q$ where $q\in T_q$ and $N(q) = \{q_1, \dots, q_{d(q)-1}, u\}$.

Case 1. $T-q$ has an isolated vertex.

By Lemma 2.4, $d(q)\geq3$. Let $T'_u = P_3\cup K_{1, 3}$ where $V(T'_u) = V(T_u)$. Then $t(T'_u) = 12$. Observe that for an M2-CIS $S'$ of $T_q$, either $q\notin S'$ or $q\in S'$ with $d_{T[S']}(q) = 1$. Let us define $t^1_q = |\{S': d_{T[S']}(q) = 1\}|$, $t_{\bar{q}} = |\{S': q\notin S'\}|$. Thus, $t(T_q) = t^1_q+t_{\bar{q}}.$

Observe that for an M2-CIS $S$ of $T$, either $u\notin S$ or $u\in S$ with $d_{T[S]}(u)\leq1$. Let

$t^0_u = |\{S: d_{T[S]}(u) = 0\}|$

 $= |\{S: d_{T[S]}(u) = 0, z\in S, d_{T[S]}(z) = 1\}|+|\{S: d_{T[S]}(u) = 0, z\in S,$

  $d_{T[S]}(z) = 0\}|$

 $\leq 2t_{\bar{q}}+(t^1_q+t_{\bar{q}}) = t^1_q+3t_{\bar{q}}$.

$t^1_u = |\{S: d_{T[S]}(u) = 1\}|$

 $= |\{S: d_{T[S]}(u) = 1, \{u, q\}\subseteq S\}|+|\{S: d_{T[S]}(u) = 1, \{w, u\}\subseteq S\}|$

 $\leq 4t^1_q+(6t_{\bar{q}}+t^1_q) = 5t^1_q+6t_{\bar{q}}$,

$t_{\bar{u}} = |\{S: u\notin S\}|$

 $= |\{S: u\notin S, w\in S, d_{T[S]}(w) = 0\}|+|\{S: u\notin S, w\in S, d_{T[S]}(w) = 1\}|$

  $+|\{S: u\notin S, w\notin S\}|$

 $= 2t^1_q+3t(T_q)+t^1_q = 3t^1_q+3t(T_q)$.

Clearly, $t(T) = t^0_u+t^1_u+t_{\bar{u}}\leq 3t(T_q)+9(t^1_q+t_{\bar{q}})$. Since $t(T_q) = t^1_q+t_{\bar{q}}$, $t(T)\leq 12t(T_q) = t(T'_u)\cdot t(T_q)$. By the induction hypothesis, $t(T_q)\leq t(F_{n-7})$. Hence, $t(T)\leq t(T'_u)\cdot t(F_{n-7})\leq t(F_n)$.

Case 2. $T-q$ has no isolated vertex.

The meanings of notations here are same as those adopted in Case 1. Let $F_1 = T-N(x)-V(P)-N(q)$, $F_2 = T-N(x)-V(P)-N(q)-N(q_i)$, $F_3 = T-N(x)-V(P)$ and $F_4 = T-N(x)-(V(P)\backslash\{q\})$. Combining these observations with the definition of $F_i$, we get that $t^0_u = 3t(F_3)$, $t^1_u = 4t(F_1)+4t(F_3)$, $t_{\bar{u}} = 2t(F_1)+3(d(q)-1)\cdot t(F_2)+3t(F_4)$. Since $t(T) = t^0_u+t^1_u+t_{\bar{u}}$, we have

Let $n_i$ be the order of $F_i$ for $i\in\{1, 2, 3, 4\}$. Then $n_3 = 3(s-2)$ and $n_4 = 3(s-2)+1$. By the induction hypothesis, $t(F_1)\leq 3^{s-2}$ and $t(F_4)\leq 4\cdot3^{s-3}$. We consider three subcases in terms of $d(q)$ ($\mod 3$).

Subcase 2.1. $d(q) = 3l, l\geq 1$

By the definition of $n_i$, $n_1 = 3(s-l-2)+1$ and $n_2\leq 3(s-l-2)$. By the induction hypothesis, $t(F_1)\leq 4\cdot3^{s-l-3}$ and $t(F_2)\leq 3^{s-l-2}$. Moreover, since $\frac{9l+5}{3^l}+11\leq 4^2$ for any $l\geq 1$, by (3.6), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.2. $d(q) = 3l+1, l\geq 1$

By the definition of $n_i$, $n_1 = 3(s-l-2)$ and $n_2\leq 3(s-l-3)+2$. By the induction hypothesis, $t(F_1)\leq 3^{s-l-2}$ and $t(F_2)\leq 4^2\cdot3^{s-l-5}$. Moreover, since $\frac{16l+18}{3^l}+33\leq 4^2\cdot3$ for any $l\geq 1$, by (3.6), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.3. $d(q) = 3l+2, l\geq 0$

By the definition of $n_i$, $n_1 = 3(s-l-3)+2$ and $n_2\leq 3(s-l-3)+1$. By the induction hypothesis, $t(F_1)\leq 4^2\cdot3^{s-l-5}$ and $t(F_2)\leq 4\cdot3^{s-l-4}$. Moreover, since $\frac{36l+44}{3^l}+99\leq 4^2\cdot3^2$ for any $l\geq 0$, by (3.6), it follows that for any $s\geq 2$ and $l\geq 0$,

By Lemma 2.2, we consider the case that there exists a vertex with one neighbor being leaf.

Claim 8. Assume that there exists a path $P: = xyz$ in $T$ with $d(x) = 1, d(y) = 2$, as shown in Figure 7. We have $t(T)\leq t(F_n)$ if one of the following conditions holds:

(1) $T-z$ has an isolated vertex or an isolated edge other than the component $xy$;

(2) $T-z$ has no isolated vertex or isolated edge, where $d(z)\geq 3$.

Proof. Let $T-yz = T_y\cup T_z$ where $z\in T_z$ and $N(z) = \{z_1, \dots, z_{d(z)-1}, y\}$.

Case 1. $T-z$ has an isolated vertex.

Let $T'_y = P_3$ where $V(T'_y) = \{x, y, z_1\}$. Then $t(T'_y) = 3$.

Subcase 1.1. $T-z$ has exactly an isolated vertex, say $z_1$.

Observe that for an M2-CIS $S'$ of $T_z-z_1$, either $z\notin S'$ or $z\in S'$ with $d_{T[S']}(z)\leq 1$. Let us define $t^0_z = |\{S': d_{T[S']}(z) = 0\}|$, $t_{\bar{z}} = |\{S': z\notin S'\}|$, $t^1_z = |\{S': d_{T[S']}(z) = 1\}|$. Thus, $t(T_z-z_1) = t^0_z+t^1_z+t_{\bar{z}}.$

Observe that for an M2-CIS $S$ of $T$, either $y\notin S$ or $y\in S$ with $d_{T[S]}(y) = 1$. Let

$t_{\bar{y}} = |\{S: y\notin S\}|\leq t(T_z-z_1)+t^1_z$,

$t^1_y = |\{S: d_{T[S]}(y) = 1\}|$

 $= |\{S: d_{T[S]}(y) = 1, \{x, y\}\subseteq S\}|+|\{S: d_{T[S]}(y) = 1, \{y, z\}\subseteq S\}|$

 $\leq t(T_z-z_1)+t^0_z+t_{\bar{z}}$,

Clearly, $t(T) = t_{\bar{y}}+t^1_y\leq 2t(T_z-z_1)+t^0_z+t^1_z+t_{\bar{z}}$. Since $t(T_z-z_1) = t^0_z+t^1_z+t_{\bar{z}}$, $t(T)\leq 3t(T_z-z_1) = t(T'_y)\cdot t(T_z-z_1)$. By the induction hypothesis, $t(T_z-z_1)\leq t(F_{n-3})$. Hence, $t(T)\leq t(T'_y)\cdot t(F_{n-3})\leq t(F_n)$.

Subcase 1.2. $T-z$ has two isolated vertices.

Observe that for an M2-CIS $S'$ of $T_z-z_1$, either $z\notin S'$ or $z\in S'$ with $d_{T[S']}(z) = 1$. Let $t_{\bar{z}} = |\{S': z\notin S'\}|$, $t^1_z = |\{S': d_{T[S']}(z) = 1\}|$. Then $t(T_z-z_1) = t_{\bar{z}}+t^1_z.$

The meanings of notations here are same as those adopted in Subcase 1.1. Note that $t_{\bar{y}}\leq2t^1_z$ and $t^1_y\leq2t_{\bar{z}}+t(T_z-z_1)$. We have $t(T) = t_{\bar{y}}+t^1_y\leq t(T_z-z_1)+2(t_{\bar{z}}+t^1_z)$. Moreover, $t(T_z-z_1) = t_{\bar{z}}+t^1_z$, $t(T)\leq 3t(T_z-z_1) = t(T'_y)\cdot t(T_z-z_1)$. By the induction hypothesis, $t(T_z-z_1)\leq t(F_{n-3})$. Hence, $t(T)\leq t(T'_y)\cdot t(F_{n-3})\leq t(F_n)$.

Case 2. $T-z$ has an isolated edge, say $z_1z^1_1$.

Let $T'_y = K_{1, 3}$ where $V(T'_y) = \{x, y, z_1, z^1_1\}$. Then $t(T'_y) = 4$. The meanings of nations here are same as those adopted in Subcase 1.1. It is sufficient to note that $t^0_z+t^1_z\leq t(T_z-z_1z^1_1)$, $t_{\bar{y}}\leq t(T_z-z_1z^1_1)+t^0_z+t^1_z$ and $t^1_y\leq2t(T_z-z_1z^1_1)$. Thus, $t(T) = t_{\bar{y}}+t^1_y\leq 4t(T_z-z_1z^1_1) = t(T'_y)\cdot t(T_z-z_1z^1_1)$. By the induction hypothesis, $t(T_z-z_1z^1_1)\leq t(F_{n-4})$. Hence, $t(T)\leq t(T'_y)\cdot t(F_{n-4})\leq t(F_n)$.

In view of Claim 8, we consider the case that $d(z) = 2$.

Claim 9. Assume that there exists a path $P: = xyzw$ in $T$ with $d(x) = 1, d(y) = d(z) = 2$, as shown in Figure 8. We have $t(T)\leq t(F_n)$ if one of the following conditions holds:

(1) $n\geq 6$, $n\equiv 0$ or $1 \; (\mod 3)$;

(2) $n\geq 8$, $n\equiv 2 \; (\mod 3)$, $d(w)\geq 3$.

Proof. Let $F_1 = T-N[y]$, $F_2 = T-V(P)$, and $F_3 = T-V(P)-N(w)$. Observe that for an M2-CIS $S$ of $T$, either $z\notin S$ or $z\in S$ with $d_{T[S]}(z)\leq 1$. Let us define

$t_{\bar{z}} = |\{S: z\notin S\}| = t(F_1)$, $t^0_z = |\{S: d_{T[S]}(z) = 0\}| = t(F_2)$,

$t^1_z = |\{S: d_{T[S]}(z) = 1\}|$

 $= |\{S: d_{T[S]}(z) = 1, \{y, z\}\subseteq S\}|+|\{S: d_{T[S]}(z) = 1, \{z, w\}\subseteq S\}|$

 $= t(F_2)+t(F_3)$.

Since $t(T) = t_{\bar{z}}+t^0_z+t^1_z$, we have

Let $n_i$ be the order of $F_i$ for each $i\in\{1, 2, 3\}$. We consider three cases in terms of the modularity of $n \; (\mod 3)$.

Case 1. $n = 3s$, $s\geq 2$.

By the definition of $n_i$, $n_1 = 3(s-1)$, $n_2 = 3(s-2)+2$. By the induction hypothesis, $t(F_1)\leq 3^{s-1}$ and $t(F_2)\leq 4^2\cdot3^{s-4}$. We distinguish three subcases according to $d(w) \; (\mod 3)$.

Subcase 1.1. $d(w) = 3l$, $l\geq 1$,

Since $n_3 = 3(s-l-1)$, by the induction hypothesis, $t(F_3)\leq 3^{s-l-1}$. Moreover, since $\frac{3^3}{3^l}+59\leq 3^4$ for any $l\geq 1$, by (3.7), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 1.2. $d(w) = 3l+1$, $l\geq 1$

Since $n_3 = 3(s-l-2)+2$, by the induction hypothesis, $t(F_3)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{4^2}{3^l}+59\leq 3^4$ for any $l\geq 1$, by (3.7), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 1.3. $d(w) = 3l+2$, $l\geq 0$

Since $n_3 = 3(s-l-2)+1$, by the induction hypothesis, $t(F_3)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{12}{3^l}+59\leq 3^4$ for any $l\geq 0$, by (3.7), it follows that for any $s\geq 2$ and $l\geq 0$,

Case 2. $n = 3s+1$, $s\geq 2$

By the definition of $n_i$, $n_1 = 3(s-1)+1$, $n_2 = 3(s-1)$, by the induction hypothesis, $t(F_1)\leq 4\cdot3^{s-2}$ and $t(F_2)\leq 3^{s-1}$.

Subcase 2.1. $d(w) = 3l$, $l\geq 1$

Since $n_3 = 3(s-l-1)+1$, by the induction hypothesis, $t(F_3)\leq 4\cdot3^{s-l-2}$. Moreover, since $\frac{4}{3^l}+10\leq 4\cdot3$ for any $l\geq 1$, by (3.7), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.2. $d(w) = 3l+1$, $l\geq 1$

Since $n_3 = 3(s-l-1)$, by the induction hypothesis, $t(F_3)\leq 3^{s-l-1}$. Moreover, since $\frac{3}{3^l}+10\leq 4\cdot3$ for any $l\geq1$, by (3.7), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 2.3. $d(w) = 3l+2$, $l\geq 0$

Since $n_3 = 3(s-l-2)+2$, by the induction hypothesis, $t(F_3)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{4^2}{3^l}+90\leq 4\cdot3^3$ for any $l\geq 0$, by (3.7), it follows that for any $s\geq 2$ and $l\geq 0$,

Case 3. $n = 3s+2$, $s\geq 2$

By the definition of $n_i$, $n_1 = 3(s-1)+2$, $n_2 = 3(s-1)+1$. By the induction hypothesis, we have $t(F_1)\leq 4^2\cdot3^{s-3}$ and $t(F_2)\leq 4\cdot3^{s-2}$.

Subcase 3.1. $d(w) = 3l$, $l\geq 1$

Since $n_3 = 3(s-l-1)+2$, by the induction hypothesis, $t(F_3)\leq 4^2\cdot3^{s-l-3}$. Moreover, since $\frac{4^2}{3^l}+40\leq 4^2\cdot3$ for any $l\geq 1$, by (3.7), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 3.2. $d(w) = 3l+1$, $l\geq 1$

Since $n_3 = 3(s-l-1)+1$, by the induction hypothesis, $t(F_3)\leq 4\cdot3^{s-l-2}$. Moreover, since $\frac{12}{3^l}+40\leq 4^2\cdot3$ for any $l\geq 1$, by (3.7), it follows that for any $s\geq 2$ and $l\geq 1$,

Subcase 3.3. $d(w) = 3l+2$, $l\geq 1$

Since $n_3 = 3(s-l-1)$, by the induction hypothesis, $t(F_3)\leq3^{s-l-1}$. Moreover, since $\frac{3^2}{3^l}+40\leq 4^2\cdot3$ for any $l\geq 1$, by (3.7), it follows that for any $s\geq 2$ and $l\geq 1$,

In view of Claim 9, we proceed to consider the case that $d(w) = 2$ and $n = 3s+2$ where $s\geq2$.

Claim 10. Assume that there exists a path $P: = xyzwu$ in $T$ with $d(x) = 1, d(y) = d(z) = d(w) = 2$, as shown in Figure 9. We have $t(T)\leq t(F_n)$ if one of the following conditions holds:

(1) $T-u$ has an isolated vertex or an isolated edge;

(2) $T-u$ has no isolated vertex or isolated edge, where $d(u)\geq4$.

Proof. Let $N(u) = \{u_1, \dots, u_{d(u)-1}, w\}$.

Case 1. $T-u$ has an isolated vertex or an isolated edge.

Subcase 1.1. $T-u$ has an isolated vertex.

Let $T-zw = T_z\cup T_w$ where $w\in T_w$. Observe that for an M2-CIS $S'$ of $T_w$, either $w\notin S'$ or $w\in S'$ with $d_{T[S']}(w)\leq 1$. Let us define $\tilde{t}^0_w = |\{S': d_{T[S']}(w) = 0\}|$, $\tilde{t}^1_w = |\{S': d_{T[S']}(w) = 1\}|$, $\tilde{t}_{\bar{w}} = |\{S': w\notin S'\}|$. Then $t(T_w) = \tilde{t}^0_w+\tilde{t}^1_w+\tilde{t}_{\bar{w}}.$

Observe that for an M2-CIS $S$ of $T$, either $w\notin S$ or $w\in S$ with $d_{T[S]}(w)\leq 1$. Let

$t^0_w = |\{S: d_{T[S]}(w) = 0\}| = \tilde{t}^0_w$,

$t^1_w = |\{S: d_{T[S]}(w) = 1\}|$

 $= |\{S: d_{T[S]}(w) = 1, \{z, w\}\subseteq S\}|+|\{S: d_{T[S]}(w) = 1, \{w, u\}\subseteq S\}|$

 $= \tilde{t}^0_w+\tilde{t}^1_w$

$t_{\bar{w}} = |\{S: w\notin S\}|$

 $= |\{S: w\notin S, u\in S, d_{T[S]}(u) = 1\}|+|\{S: w\notin S, u\notin S\}|$

 $\leq 3\tilde{t}_{\bar{w}}+\tilde{t}^0_w$.

It is easy to see that $t(T) = t^0_w+t^1_w+t_{\bar{w}}\leq 3\tilde{t}^0_w+\tilde{t}^1_w+3\tilde{t}_{\bar{w}}$. Since $t(T_w) = \tilde{t}^0_w+\tilde{t}^1_w+\tilde{t}_{\bar{w}}$, $t(T)\leq 3t(T_w) = t(T_z)\cdot t(T_w)$. By the induction hypothesis, $t(T_w)\leq t(F_{n-3})$. Hence, $t(T)\leq t(T_z)\cdot t(F_{n-3})\leq t(F_n)$.

Subcase 1.2. $T-u$ has an isolated edge.

Let $T-wu = T_w\cup T_u$ where $u\in T_u$ and $T'_w = K_{1, 3}$ where $V(T'_w) = V(T_w)$. Then $t(T'_w) = 4$. Observe that for an M2-CIS $S'$ of $T_u$, either $u\notin S'$ or $u\in S' \; d_{T[S']}(u)\leq 1$. Let us define $t^0_u = |\{S': d_{T[S']}(u) = 0\}|$, $t_{\bar{u}} = |\{S': u\notin S'\}|$, $t^1_u = |\{S': d_{T[S']}(u) = 1\}|$. Then $t(T_u) = t^0_u+t^1_u+t_{\bar{u}}.$

The meanings of notations here are same as those adopted in Subcase 1.1. Note that $t^0_w = t_{\bar{u}}$, $t^1_w\leq t^1_u+t_{\bar{u}}$ and $t_{\bar{w}} = t(T_u)+t^0_u+2t^1_u$.

Thus, $t(T) = t^0_w+t^1_w+t_{\bar{w}}\leq t(T_u)+t^0_u+3t^1_u+2t_{\bar{u}}$. Moreover, $t(T_u) = t^0_u+t^1_u+t_{\bar{u}}$, $t(T)\leq 4t(T_u) = t(T'_w)\cdot t(T_u)$. By the induction hypothesis, $t(T_u)\leq t(F_{n-4})$. Hence, $t(T)\leq t(T'_w)\cdot t(F_{n-4})\leq t(F_n)$.

Case 2. $T-u$ has no isolated vertex or isolated edge, where $d(u)\geq4$.

The meanings of notations here are same as those adopted in Subcase 1.1. Let $F_1 = T-(V(P)\setminus \{u\})$, $F_2 = T-V(P)$, $F_3 = T-V(P)-N(u)$ and $F_4 = T-V(P)-N(u)-N(u_i)$. Combining these observations with the definition of $F_i$, we get that $t^0_w = t(F_2)$, $t^1_w = t(F_2)+t(F_3)$ and $t_{\bar{w}} = t(F_1)+t(F_3)+2(d(u)-1)\cdot t(F_4)$. Since $t(T) = t^0_w+t^1_w+t_{\bar{w}}$, we have

Let $n_i$ be the order of $F_i$ for each $i\in\{1, 2, 3, 4\}$. Then $n_1 = 3(s-1)+1$, $n_2 = 3(s-1)$. By the induction hypothesis, $t(F_1)\leq 4\cdot3^{s-2}$ and $t(F_2)\leq 3^{s-1}$. We want to prove that $t(T)\leq 4^2\cdot3^{s-2} = t(F_n)$ for any $s\geq 2$. By (3.8), we complete the proof by showing that for any $s\geq 2$,

Subcase 2.1. $d(u) = 3l$, $l\geq 2$

Since $n_3 = 3(s-l-1)+1$, $n_4\leq 3(s-l-1)$, by the induction hypothesis, $t(F_3)\leq 4\cdot3^{s-l-2}$ and $t(F_4)\leq 3^{s-l-1}$. Moreover, since $\frac{9l+1}{3^l}\leq 3$ for any $l\geq 2$, it follows that for any $s\geq 2$ and $l\geq 2$,

i.e., (3.9) holds.

Subcase 2.2. $d(u) = 3l+1$, $l\geq 0$

Since $n_3 = 3(s-l-1)$, $n_4\leq 3(s-l-2)+2$, by the induction hypothesis, $t(F_3)\leq 3^{s-l-1}$ and $t(F_4)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{16l+9}{3^l}\leq 3^2$ for any $l\geq 0$, it follows that for any $s\geq 2$ and $l\geq 0$,

i.e., (3.9) holds.

Subcase 2.3. $d(u) = 3l+2$, $l\geq 1$

Since $n_3 = 3(s-l-2)+2$, $n_4\leq 3(s-l-2)+1$, by the induction hypothesis, $t(F_3)\leq 4^2\cdot3^{s-l-4}$ and $t(F_4)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{36l+28}{3^l}\leq 3^3$ for any $l\geq 1$, it follows that for any $s\geq 2$ and $l\geq 1$,

i.e., (3.9) holds.

In view of Claim 10, we proceed to consider the case that $d(u) = 2$ and $d(u) = 3$ respectively.

Claim 11. Assume that there exists a path $P: = xyzwuq$ in $T$ with $d(x) = 1, d(y) = d(z) = d(w) = d(u) = 2$, as shown in Figure 10. We have $t(T)\leq t(F)$.

Proof. Let $N(q) = \{q_1, \dots, q_{d(q)-1}, u\}$ and $T-wu = T_w\cup T_u$ where $u\in T_u$.

Case 1. $T-q$ has an isolated vertex.

Let $T'_w = K_{1, 3}$ where $V(T'_w) = V(T_w)$. Then $t(T'_w) = 4$. Observe that for an M2-CIS $S'$ of $T_u$, either $u\notin S'$ or $u\in S'$ with $d_{T[S']}(u)\leq 1$. Let us define $\tilde{t}^0_u = |\{S': d_{T[S']}(u) = 0\}|$, $\tilde{t}_{\bar{u}} = |\{S': u\notin S'\}|$, $\tilde{t}^1_u = |\{S': d_{T[S']}(u) = 1\}|$. Thus, $t(T_u) = \tilde{t}^0_u+\tilde{t}^1_u+\tilde{t}_{\bar{u}}.$

Observe that for an M2-CIS $S$ of $T$, either $u\notin S$ or $u\in S$ with $d_{T[S]}(u)\leq1$. Let

$t^0_u = |\{S: d_{T[S]}(u) = 0\}| = 2\tilde{t}^0_u$,

$t^1_u = |\{S: d_{T[S]}(u) = 1\}|$

 $= |\{S: d_{T[S]}(u) = 1, \{w, u\}\subseteq S\}|+|\{S: d_{T[S]}(u) = 1, \{u, q\}\subseteq S\}|$

 $= \tilde{t}^0_u+3\tilde{t}^1_u$.

$t_{\bar{u}} = |\{S: u\notin S\}|$

 $= |\{S: u\notin S, w\notin S\}|+|\{S: u\notin S, w\in S, d_{T[S]}(w) = 1\}|+|\{S: u\notin S,$

  $w\in S, d_{T[S]}(w) = 0\}|$

 $= \tilde{t}_{\bar{u}}+(\tilde{t}^0_u+\tilde{t}_{\bar{u}})+\tilde{t}_{\bar{u}} = \tilde{t}^0_u+3\tilde{t}_{\bar{u}}$.

Then $t(T) = t^0_u+t^1_u+t_{\bar{u}} = 4\tilde{t}^0_u+3\tilde{t}^1_u+3\tilde{t}_{\bar{u}}$. Moreover, $t(T_u) = \tilde{t}^0_u+\tilde{t}^1_u+\tilde{t}_{\bar{u}}$, $t(T)\leq 4t(T_u) = t(T'_w)\cdot t(T_u)$. By the induction hypothesis, $t(T_u)\leq t(F_{n-4})$. Hence, $t(T)\leq t(T'_w)\cdot t(T_u)\leq t(F_{n-4})$.

Case 2. $T-q$ has no isolated vertex.

The meanings of notations here are same as those adopted in Case 1. Let $F_1 = T-V(P)-N(q)$, $F_2 = T-V(P)-N(q)-N(q_i)$, $F_3 = T-V(P)$ and $F_4 = T-(V(P)\backslash\{q\})$. Combining these observations with the definition of $F_i$, we get that $t^0_u = 2t(F_3)$, $t^1_u = 3t(F_1)+t(F_3)$ and $t_{\bar{u}} = t(F_1)+2(d(q)-1)\cdot t(F_2)+t(F_4)$. Since $t(T) = t^0_u+t^1_u+t_{\bar{u}}$, we have

Let $n_i$ be the order of $F_i$ for $i\in \{1, 2, 3, 4\}$. Then $n_3 = 3(s-2)+2$, $n_4 = 3(s-1)$. By the induction hypothesis, $t(F_3)\leq 4^2\cdot3^{s-4}$ and $t(F_4)\leq 3^{s-1}$. We want to prove that $t(T)\leq 4^2\cdot3^{s-2} = t(F_n)$ for any $s\geq 2$. By (3.10), we complete the {proof} by showing that for any $s\geq 2$,

Subcase 2.1. $d(q) = 3l$, $l\geq 1$

$n_1 = 3(s-l-1)$, $n_2\leq 3(s-l-2)+2$, by the induction hypothesis, $t(F_1)\leq 3^{s-l-1}$ and $t(F_2)\leq 4^2\cdot3^{s-l-4}$. Moreover, since $\frac{96l+76}{3^l}\leq 23\cdot3$ for any $l\geq 1$, it follows that for any $s\geq 2$ and $l\geq 1$,

i.e., (3.11) holds.

Subcase 2.2. $d(q) = 3l+1$, $l\geq 0$

$n_1 = 3(s-l-2)+2$, $n_2\leq 3(s-l-2)+1$, by the induction hypothesis, $t(F_1)\leq 4^2\cdot3^{s-l-4}$ and $t(F_2)\leq 4\cdot3^{s-l-3}$. Moreover, since $\frac{72l+64}{3^l}\leq 23\cdot3$ for any $l\geq 0$, it follows that for any $s\geq 2$ and $l\geq 0$,

i.e., (3.11) holds.

Subcase 2.3. $d(q) = 3l+2$, $l\geq 0$

$n_1 = 3(s-l-2)+1$, $n_2\leq 3(s-l-2)$, by the induction hypothesis, $t(F_1)\leq 4\cdot3^{s-l-3}$ and $t(F_2)\leq 3^{s-l-2}$. Moreover, since $\frac{18l+22}{3^l}\leq 23$ for any $l\geq 0$, it follows that for any $s\geq 2$ and $l\geq 0$,

i.e., (3.11) holds.

Claim 12. Assume that there exists a vertex $x$ with $d(x)\geq 3$ such all components of $T-x$ are isomorphic to $K_{1, 3}$, but one, denoted by $T_y$ where $y$ is the neighbor of $x$ lying in $T_y$, is not isomorphic to $K_{1, 3}$, as shown in Figure 11. We have $t(T)\leq t(F_n)$.

Proof. For an integer $a\geq 2$, assume that $N(x) = \{x_1, \dots, x_a, y\}$. Let $T-xy = T_x\cup T_y$ where $y\in T_y$. Then $|V(T_x)| = 4a+1$.

Case 1. $T-y$ has no isolated vertex.

Observe that for an M2-CIS $S'$ of $T_y$, either $y\notin S'$ or $y\in S'$ with $d_{T[S']}(y)\leq 1$. Let us define $t^0_y = |\{S': d_{T[S']}(y) = 0\}|$, $t_{\bar{y}} = |\{S': y\notin S'\}|$, $t^1_y = |\{S': d_{T[S']}(y) = 1\}|$. Thus, $t(T_y) = t^0_y+t^1_y+t_{\bar{y}}.$

Observe that for an M2-CIS $S$ of $T$, either $x\notin S$ or $x\in S$ with $d_{T[S]}(x)\leq 1$. Let

$t^0_x = |\{S: d_{T[S]}(x) = 0\}|\leq 2^a\cdot(t^1_y+t_{\bar{y}})$,

$t^1_x = |\{S: d_{T[S]}(x) = 1\}|$

 $= |\{S: d_{T[S]}(x) = 1, y\in S\}|+|\{S: d_{T[S]}(x) = 1, y\notin S\}|$

 $\leq 3^a\cdot(t^0_y+t_{\bar{y}})+a\cdot3^{a-1}\cdot t(T_y)$,

$t_{\bar{x}y} = |\{S: x\notin S, d_{T[S]}(x_i) = 1\; or\; d_{T[S]}(x_i) = d_{T[S]}(x_j) = 0, i, j\in \{1, \dots, a\}\}|$

 $= (4^a-2^a-a\cdot2^{a-1})\cdot t(T_y)$,

$t^1_{\bar{x}y} = |\{S: x\notin S, d_{T[S]}(y) = 1, d_{T[S]}(x_i)\neq1, \exists \; exactly\; one\; x_i, d_{T[S]}(x_i) =$

  $0\; or\; x_i\notin S, i\in \{1, \dots, a\}\}|$

 $= (2^a+a\cdot2^{a-1})\cdot t^1_y$,

$t^0_{\bar{x}y} = |\{S: x\notin S, d_{T[S]}(y) = 0, d_{T[S]}(x_i)\neq 1, x_i\notin S, i\in \{1, \dots, a\}\}|$

 $= a\cdot2^{a-1}\cdot t^0_y$,

$t_{\bar{x}} = |\{S: x\notin S\}| = t_{\bar{x}y}+t^1_{\bar{x}y}+t^0_{\bar{x}y}$

 $= (4^a-2^a-a\cdot2^{a-1})\cdot t(T_y)+(2^a+a\cdot2^{a-1})\cdot t^1_y+a\cdot2^{a-1}\cdot t^0_y$.

Since $t(T_y) = t^0_y+t^1_y+t_{\bar{y}}$, $(2^{a+1}+a\cdot2^{a-1})\cdot t^1_y+(3^a+a\cdot2^{a-1})\cdot t^0_y+(3^a+2^a)\cdot t_{\bar{y}}\leq (3^a+a\cdot2^{a-1})\cdot t(T_y)$. Moreover, $t(T) = t^0_x+t^1_x+t_{\bar{x}}$. We get that

Let $V(T'_x) = V(T_x)$. Then $t(T'_x\cup T_y) = t(T'_x)\cdot t(T_y)$. By the induction hypothesis, $t(T_y)\leq t(F_{n-(4a+1)})$. We want to prove $t(T)\leq t(T'_x)\cdot t(F_{n-(4a+1)})\leq t(F_n)$ for any $a\geq 2$. Therefore, we need to show that for any $a\geq 2$,

We distinguish into three cases based on the modularity of $a \; (\mod 3)$.

Subcase 1.1. $a = 3s$, $s\geq 1$

Let $T'_x = (4s-1)P_3\cup K_{1, 3}$ where $|V(T'_x)| = 12s+1$. Then $t(T'_x) = 4\cdot3^{4s-1}$. Since $4^{3s}\leq3^{4s}$ and $(s+1)3^{3s}\leq3^{4s-1}$ for any $s\geq 2$, by (3.12), it follows that for any $s\geq 2$,

If $s = 1$, then $a = 3$. Note that $t^0_x\leq8(t^1_y+t_{\bar{y}})$, $t^1_x\leq 23t^0_y+25t_{\bar{y}}+29t(T_y)$ and $t_{\bar{x}} = 44t(T_y)+20t^1_y+12t^0_y$. Meanwhile, $t(T_y) = t^0_y+t^1_y+t_{\bar{y}}$, $t(T)\leq 108t(T_y) = t(T'_x)\cdot t(T_y)$. By the induction hypothesis, $t(T_y)\leq t(F_{n-(4a+1)})$. Hence, $t(T)\leq t(T'_x)\cdot t(F_{n-(4a+1)})\leq t(F_n)$.

Subcase 1.2. $a = 3s+1$, $s\geq 1$

Let $T'_x = (4s-1)P_3\cup2K_{1, 3}$ where $|V(T'_x)| = 3(4s+1)+2$. Then $t(T'_x) = 4^2\cdot3^{4s-1}$. Since $4^{3s+1}\leq 4\cdot3^{4s}$ and $(3s+4)3^{3s}\leq 4\cdot3^{4s-1}$ for any $s\geq 2$, by (3.12), it follows that for any $s\geq 2$,

The result is true for $s = 1$.

Subcase 1.3. $a = 3s+2$, $s\geq 0$

Let $T'_x = (4s+3)P_3$ where $|V(T'_x)| = 3(4s+3)$. Then $t(T'_x) = 3^{4s+3}$. Since $4^{3s+2}\leq4^2\cdot3^{4s}$ and $(3s+5)\cdot3^{3s+1}\leq11\cdot3^{4s}$ for any $s\geq 1$, by (3.12), it follows that for any $s\geq 1$,

The result is true for $s = 0$.

Case 2. $T-y$ has an isolated vertex.

By Lemma 2.4, $d(y)\geq3$. The meanings of notations here are same as those adopted in Case 1. Thus $t(T_y) = t^1_y+t_{\bar{y}}, t^0_x\leq 2^{a+1}\cdot t_{\bar{y}}, t^1_x\leq a\cdot3^{a-1}\cdot t(T_y)$, $t_{\bar{x}}\leq(4^a-2^a-a\cdot2^{a-1})\cdot t(T_y)+(2^a+a\cdot2^{a-1})\cdot t^1_y$.

Furthmore, $2^{a+1}\cdot t_{\bar{y}}+(2^a+a\cdot2^{a-1})\cdot t^1_y\leq (3^a+a\cdot2^{a-1})\cdot t(T_y)$, $t(T)\leq [4^a+(a+3)3^{a-1}-2^a]\cdot t(T_y).$ By a similar argument as in the proof of Case 1, we show that $t(T)\leq t(F_n)$.

In view of Claim 11, it remains to consider the case that $d(u) = 3$.

Claim 13. Assume that there exists a path $P: = xyzwu$ in $T$ with $d(x) = 1, d(y) = d(z) = d(w) = 2, d(u) = 3$. If $T-u$ has no isolated vertex or isolated edge, then $t(T)\leq t(F_n)$.

Proof. By Claims 1–12, it is not difficult to observe that there exists a vertex $x$ such that $T-x$ has two components, one is isomorphic to $P_4$, the other one is isomorphic to $P_4$ or $K_{1, 3}$, as shown in Figure 12. The meanings of notations adopted here are same in Case 1 of Claim 12. Let $T-xy = T_x\cup T_y$ where $y\in T_y$ and $T'_x = 3P_3$ where $V(T'_x) = V(T_x)$. Then $t(T'_x) = 3^3$.

Case 1. $T-x$ has two components which are isomorphic to $P_4$.

Subcase 1.1. $T-y$ has no isolated vertex.

Note that $t^0_x\leq 4(t^0_y+t_{\bar{y}})$, $t^1_x\leq 6t(T_y)+9(t^0_y+t^1_y)$, $t_{\bar{x}}\leq 6t(T_y)+3t^1_y+2t^0_y$. Meanwhile, $t(T) = t^0_x+t^1_x+t_{\bar{x}}$. This implies that $t(T)\leq 12t(T_y)+15t^0_y+12t^1_y+4t_{\bar{y}}.$ Since $t(T_y) = t^0_y+t^1_y+t_{\bar{y}}$, $t(T)\leq 3^3t(T_y) = t(T'_x)\cdot t(T_y)$. By the induction hypothesis, $t(T_y)\leq t(F_{n-9})$. Hence, $t(T)\leq t(T'_x)\cdot t(F_{n-9})\leq t(F_n)$.

Subcase 1.2. $T-y$ has an isolated vertex.

By Lemma 2.4, $d(y)\geq 3$. Note that $t^0_x\leq 4t(T_y)$, $t^1_x\leq 9t^1_y+6t_{\bar{y}}$ and $t_{\bar{x}}\leq 6t(T_y)+3t^1_y$. Since $t(T) = t^0_x+t^1_x+t_{\bar{x}}$, $t(T)\leq 10t(T_y)+12t^1_y+6t_{\bar{y}}.$ Moreover, $t(T_y) = t^1_y+t_{\bar{y}}$, $t(T)\leq 22t(T_y)\leq 3^3t(T_y) = t(T'_x)\cdot t(T_y)$. By the induction hypothesis, $t(T_y)\leq t(F_{n-9})$. Hence, $t(T)\leq t(T'_x)\cdot t(F_{n-9})\leq t(F_n)$.

Case 2. $T-x$ has two components which are isomorphic to $P_4$ and $K_{1, 3}$, respectively.

Subcase 2.1. $T-y$ has no isolated vertex.

Note that $t^1_x\leq 6t(T_y)+9(t^0_y+t_{\bar{y}})$, $t^0_x\leq 4(t^1_y+t_{\bar{y}})$, $t_{\bar{x}}\leq7 t(T_y)+5t^1_y+3t^0_y$. Since $t(T) = t^0_x+t^1_x+t_{\bar{x}}$, $t(T)\leq 13t(T_y)+12t^0_y+9t^1_y+13t_{\bar{y}}.$ Moreover, $t(T_y) = t^0_y+t^1_y+t_{\bar{y}}$ and $t(T)\leq 26t(T_y)\leq 3^3t(T_y) = t(T'_x)\cdot t(T_y)$. By the induction hypothesis, $t(T_y)\leq t(F_{n-9})$. Hence, $t(T)\leq t(T'_x)\cdot t(F_{n-9})\leq t(F_n)$.

Subcase 2.2. $T-y$ has an isolated vertex.

By Lemma 2.4, $d(y)\geq3$. Note that $t^1_x\leq 9(t^1_y+t_{\bar{y}})$, $t^0_x\leq 4t(T_y)$ and $t_{\bar{x}}\leq 7t(T_y)+5t^1_y$. Since $t(T) = t^0_x+t^1_x+t_{\bar{x}}$, $t(T)\leq 11t(T_y)+14t^1_y+9t_{\bar{y}}.$ Moreover, $t(T_y) = t^1_y+t_{\bar{y}}$ and $t(T)\leq 25t(T_y)\leq3^3t(T_y) = t(T'_x)\cdot t(T_y)$. By the induction hypothesis, $t(T_y)\leq t(F_{n-9})$. Hence, $t(T)\leq t(T'_x)\cdot t(F_{n-9})\leq t(F_n)$.

From the above discussion, we proceed to consider the following.

Claim 14. Assume there exists a path $P: = xyz$ in $T$ with $d(x) = 1$ or $d(x) = 3$ such that two neighbors of $x$ distinct from $y$ being leaves, $d(y) = 2$ and $d(z)\geq3$. If $T-z$ has no isolated vertex or isolated edge, then $t(T)\leq t(F_n)$.

Proof. By Claims 1–11 and 13, it remains to consider the case that there exists a vertex $w$ such that $T-w$ has at least two components which are isomorphic to $K_{1, 3}$. By Lemma 2.4 and Claim 12, we have $t(T)\leq t(F_n)$.

This completes the proof of theorem.

4.   Conclusions

In this paper, we determine the maximum number of maximal 2-component independent sets of a forest of order $n$. It is an interesting problem to determine the maximum number of maximal 2-component independent sets of graphs of order $n$ over some other families, such as trees, bipartite graphs, triangle-free graphs, all connected graphs.

Acknowledgment

The work was supported by the national natural science foundation of China (No. 12061073) and XJEDU2019I001.

Conflict of interest

The authors declare no conflict of interests.