ABSTRACT

A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) G with vertex set $V\left(G\right)$ is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex $x\in V\left(G\right)$ such that $G-x$ is a tree (respectively, forest). In this paper, we survey on the large numbers of maximal independent sets among all trees, forests, quasi-trees and quasi-forests. In addition, we further look into the problem of determining the third largest number of maximal independent sets among all quasi-trees and quasi-forests. Extremal graphs achieving these values are also given.

Keywords:

Maximal Independent Set, Quasi-Tree Graph, Quasi-Forest Graph, Extremal Graph

1. Introduction and Preliminary

Let $G=\left(V,E\right)$ be a simple undirected graph. An independent set is a subset S of V such that no two vertices in S are adjacent. A maximal independent set is an independent set that is not a proper subset of any other independent set. The set of all maximal independent sets of a graph G is denoted by $\text{MI}\left(G\right)$ and its cardinality by $mi\left(G\right)$ .

The problem of determining the largest value of $mi\left(G\right)$ in a general graph of order n and those graphs achieving the largest number was proposed by Erdös and Moser, and solved by Moon and Moser [1] . It was then studied for various families of graphs, including trees, forests, (connected) graphs with at most one cycle, (connected) triangle-free graphs, (k-)connected graphs, bipartite graphs; for a survey see [2] . Jin and Li [3] investigated the second largest number of $mi\left(G\right)$ among all graphs of order n; Jou and Lin [4] further explored the same problem for trees and forests; Jin and Yan [5] solved the third largest number of $mi\left(G\right)$ among all trees of order n. A connected graph (respectively, graph) G with vertex set $V\left(G\right)$ is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex $x\in V\left(G\right)$ such that $G-x$ is a tree (respectively, forest). The concept of quasi-tree graphs was mentioned by Liu and Lu in [6] . Recently, the problem of determining the largest and the second largest numbers of $mi\left(G\right)$ among all quasi-tree graphs and quasi-forest graphs of order n was solved by Lin [7] [8] .

In this paper, we survey on the large numbers of maximal independent sets among all trees, forests, quasi-trees and quasi-forests. In addition, we further look into the problem of determining the third largest number of maximal independent sets among all quasi-trees and quasi-forests. Extremal graphs achieving these values are also given.

For a graph $G=\left(V,E\right)$ , the neighborhood $N_G\left(x\right)$ of a vertex x is the set of vertices adjacent to x in G and the closed neighborhood $N_G\left[x\right]$ is $\left\{x\right\}\cup N_G\left(x\right)$ . The degree of x is the cardinality of $N_G\left(x\right)$ , denoted by ${{\displaystyle deg}}_G\left(x\right)$ . For a set $A\subseteq V\left(G\right)$ , the deletion of A from G is the graph $G-A$ obtained from G by removing all vertices in A and their incident edges. Two graphs $G_1$ and $G_2$ are disjoint if $V\left(G_1\right)\cap V\left(G_2\right)=\varnothing$ . The union of two disjoint graphs $G_1$ and $G_2$ is the graph $G_1\cup G_2$ with vertex set $V\left(G_1\cup G_2\right)=V\left(G_1\right)\cup V\left(G_2\right)$ and edge set $E\left(G_1\cup G_2\right)=E\left(G_1\right)\cup E\left(G_2\right)$ . $nG$ is the short notation for the union of n copies of disjoint graphs isomorphic to G. Denote by $C_n$ a cycle with n vertices and $P_n$ a path with n vertices.

Throughout this paper, for simplicity, let $r=\sqrt{2}$ .

Lemma 1.1 ( [9] ) For any vertex x in a graph G, $mi\left(G\right)\le mi\left(G-x\right)+mi\left(G-N_G\left[x\right]\right)$ .

Lemma 1.2 ( [10] ) If G is the union of two disjoint graphs $G_1$ and $G_2$ , then $mi\left(G\right)=mi\left(G_1\right)mi\left(G_2\right)$ .

2. Survey on the Large Numbers of Maximal Independent Sets

In this section, we survey on the large numbers of maximal independent sets among all trees, forests, quasi-trees and quasi-forests. The results of the largest numbers of maximal independent sets among all trees and forests are described in Theorems 2.1 and 2.2, respectively.

Theorem 2.1 ( [10] [11] ) If T is a tree with $n\ge 1$ vertices, then $mi\left(T\right)\le t_1\left(n\right)$ , where

$t_1\left(n\right)=\{\begin{array}{ll}{r}^{n-2}+1,\hfill & \text{if}n\text{is}\text{even,}\hfill \\ r^{n-1},\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

Furthermore, $mi\left(T\right)=t_1\left(n\right)$ if and only if $T\in T_1\left(n\right)$ , where

$T_1\left(n\right)=\{\begin{array}{ll}B\left(2,\frac{n-2}{2}\right)\text{or}B\left(4,\frac{n-4}{2}\right),\hfill & \text{if}n\text{is}\text{even,}\hfill \\ B\left(1,\frac{n-1}{2}\right),\hfill & \text{if}n\text{is}\text{odd,}\hfill \end{array}$

where $B\left(i\mathrm{,}j\right)$ is the set of batons, which are the graphs obtained from the basic path P of $i\ge 1$ vertices by attaching $j\ge 0$ paths of length two to the endpoints of P in all possible ways (see Figure 1).

Theorem 2.2 ( [10] [11] ) If F is a forest with $n\ge 1$ vertices, then $mi\left(F\right)\le f_1\left(n\right)$ , where

$f_1\left(n\right)=\{\begin{array}{ll}{r}^n,\hfill & \text{if}n\text{is}\text{even,}\hfill \\ r^{n-1},\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

Furthermore, $mi\left(F\right)=f_1\left(n\right)$ if and only if $F\in F_1\left(n\right)$ , where

$F_1\left(n\right)=\{\begin{array}{ll}\frac{n}{2}{P}_2,\hfill & \text{if}n\text{is}\text{even,}\hfill \\ B\left(1;\frac{n-1-2s}{2}\right)\cup s{P}_2\text{for}\text{some}s\text{with}0\le s\le \frac{n-1}{2},\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

The results of the second largest numbers of maximal independent sets among all trees and forests are described in Theorems 2.3 and 2.4, respectively.

Theorem 2.3 ( [4] ) If T is a tree with $n\ge 4$ vertices having $T\notin T_1\left(n\right)$ , then $mi\left(T\right)\le t_2\left(n\right)$ , where

$t_2\left(n\right)=\{\begin{array}{ll}{r}^{n-2},\hfill & \text{if}n\ge 4\text{is}\text{even},\hfill \\ 3,\hfill & \text{if}n=5,\hfill \\ 3r^{n-5}+1,\hfill & \text{if}n\ge 7\text{is}\text{odd}.\hfill \end{array}$

Furthermore, $mi\left(T\right)=t_2\left(n\right)$ if and only if $T={T^{\prime }}_2\left(8\right),{T^{″}}_2\left(8\right),P_{10}$ or $T\in T_2\left(n\right)$ , where $T_2\left(n\right)$ and ${T^{\prime }}_2\left(8\right)$ , ${T^{″}}_2\left(8\right)$ are shown in Figure 2 and Figure 3, respectively.

Theorem 2.4 ( [4] ) If F is a forest with $n\ge 4$ vertices having $F\notin F_1\left(n\right)$ , then $mi\left(F\right)\le f_2\left(n\right)$ , where

$f_2\left(n\right)=\{\begin{array}{ll}3r^{n-4},\hfill & \text{if}n\ge 4\text{is}\text{even},\hfill \\ 3,\hfill & \text{if}n=5,\hfill \\ 7r^{n-7},\hfill & \text{if}n\ge 7\text{is}\text{odd}.\hfill \end{array}$

Furthermore, $mi\left(F\right)=f_2\left(n\right)$ if and only if $F\in F_2\left(n\right)$ , where

$F_2\left(n\right)=\{\begin{array}{ll}{P}_4\cup \frac{n-4}{2}{P}_2,\hfill & \text{if}n\ge 4\text{is}\text{even},\hfill \\ T_2\left(5\right)\text{or}{P}_4\cup P_1,\hfill & \text{if}n=5,\hfill \\ P_7\cup \frac{n-7}{2}{P}_2,\hfill & \text{if}n\ge 7\text{is}\text{odd}.\hfill \end{array}$

The results of the third largest numbers of maximal independent sets among all trees and forests are described in Theorems 2.5 and 2.6, respectively.

Theorem 2.5 ( [5] ) If T is a tree with $n\ge 7$ vertices having $T\notin T_i\left(n\right)$ , $i=1,2$ , then $mi\left(T\right)\le t_3\left(n\right)$ , where

$t_3\left(n\right)=\{\begin{array}{ll}3r^{n-5},\hfill & \text{if}n\ge 7\text{is}\text{odd},\hfill \\ 7,\hfill & \text{if}n=8,\hfill \\ 15,\hfill & \text{if}n=10,\hfill \\ 7r^{n-8}+2,\hfill & \text{if}n\ge 12\text{is}\text{even}.\hfill \end{array}$

Furthermore, $mi\left(T\right)=t_3\left(n\right)$ if and only if $T=T_3\left(8\right),{T^{\prime }}_3\left(10\right),{T^{″}}_3\left(10\right)$ or $T\in T_3\left(n\right)$ , where $T_3\left(8\right),{T^{\prime }}_3\left(10\right),{T^{″}}_3\left(10\right),T_3\left(n\right)$ are shown in Figure 4 and Figure 5, respectively.

Theorem 2.6 ( [12] ) If F is a forest with $n\ge 8$ vertices having $F\notin F_i\left(n\right)$ , $i=1,2$ , then $mi\left(F\right)\le f_3\left(n\right)$ , where

$f_3\left(n\right)=\{\begin{array}{ll}5r^{n-6},\hfill & \text{if}n\text{is}\text{even,}\hfill \\ 13r^{n-9},\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

Furthermore, $mi\left(F\right)=f_3\left(n\right)$ if and only if $F\in F_3\left(n\right)$ , where

$F_3\left(n\right)=\{\begin{array}{ll}{T}_1\left(6\right)\cup \frac{n-6}{2}{P}_2,\hfill & \text{if}n\text{is}\text{even,}\hfill \\ T_2\left(9\right)\cup \frac{n-9}{2}{P}_2,\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

The results of the largest numbers of maximal independent sets among all quasi-tree graphs and quasi-forest graphs are described in Theorems 2.7 and 2.8, respectively.

Theorem 2.7 ( [7] ) If Q is a quasi-tree graph with $n\ge 5$ vertices, then $mi\left(Q\right)\le q_1\left(n\right)$ , where

$q_1\left(n\right)=\{\begin{array}{ll}3r^{n-4},\hfill & \text{if}n\text{is}\text{even,}\hfill \\ r^{n-1}+1,\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

Furthermore, $mi\left(Q\right)=q_1\left(n\right)$ if and only if $Q=C_5$ or $Q\in Q_1\left(n\right)$ , where $Q_1\left(n\right)$ is shown in Figure 6.

Theorem 2.8 ( [7] )If Q is a quasi-forest graph with $n\ge 2$ vertices, then $mi\left(Q\right)\le {\bar{q}}_1\left(n\right)$ , where

${\bar{q}}_1\left(n\right)=\{\begin{array}{ll}{r}^n,\hfill & \text{if}n\text{is}\text{even,}\hfill \\ 3r^{n-3},\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

Furthermore, $mi\left(Q\right)={\bar{q}}_1\left(n\right)$ if and only if $Q\in {\bar{Q}}_1\left(n\right)$ , where

${\bar{Q}}_1\left(n\right)=\{\begin{array}{ll}\frac{n}{2}{P}_2,\hfill & \text{if}n\text{is}\text{even,}\hfill \\ C_3\cup \frac{n-3}{2}{P}_2,\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

The results of the second largest numbers of maximal independent sets among all quasi-tree graphs and quasi-forest graphs are described in Theorems 2.9 and 2.10, respectively.

Theorem 2.9 ( [8] )If Q is a quasi-tree graph with $n\ge 6$ vertices having $Q\notin Q_1\left(n\right)$ , then $mi\left(Q\right)\le q_2\left(n\right)$ , where

$q_2\left(n\right)=\{\begin{array}{ll}5r^{n-6}+1,\hfill & \text{if}n\text{is}\text{even,}\hfill \\ r^{n-1},\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

Furthermore, $mi\left(Q\right)=q_2\left(n\right)$ if and only if $Q\in Q_2\left(n\right)$ , where

$Q_2\left(n\right)=\{\begin{array}{ll}{Q}_{2e}^{\left(1\right)}\left(n\right),Q_{2e}^{\left(2\right)}\left(n\right),Q_{2e}^{\left(3\right)}\left(n\right),Q_{2e}^{\left(4\right)}\left(n\right),\hfill & \text{if}n\text{is}\text{even,}\hfill \\ B\left(1,\frac{n-1}{2}\right),Q_{2o}^{\left(1\right)}\left(7\right),Q_{2o}^{\left(2\right)}\left(7\right),Q_{2o}^{\left(3\right)}\left(7\right),Q_{2o}^{\left(4\right)}\left(7\right),\hfill & \text{if}n\text{is}\text{odd,}\hfill \end{array}$

where $Q_2\left(n\right)$ is shown in Figure 7 and Figure 8.

Theorem 2.10 ( [8] )If Q is a quasi-forest graph with $n\ge 4$ vertices having $Q\notin {\bar{Q}}_1\left(n\right)$ , then $mi\left(Q\right)\le {\bar{q}}_2\left(n\right)$ , where

${\bar{q}}_2\left(n\right)=\{\begin{array}{ll}3r^{n-4},\hfill & \text{if}n\text{is}\text{even,}\hfill \\ 5r^{n-5},\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

Furthermore, $mi\left(Q\right)={\bar{q}}_2\left(n\right)$ if and only if $Q\in {\bar{Q}}_2\left(n\right)$ , where

${\bar{Q}}_2\left(n\right)=\{\begin{array}{ll}{P}_4\cup \frac{n-4}{2}{P}_2,Q_1\left(n-2s\right)\cup s{P}_2,\hfill & \hfill \\ Q_2\left(6\right)\cup \frac{n-6}{2}{P}_2,C_3\cup B\left(1,\frac{n-4-2s}{2}\right)\cup s{P}_2,\hfill & \text{if}n\text{is}\text{even,}\hfill \\ Q_1\left(5\right)\cup \frac{n-5}{2}{P}_2,W\cup \frac{n-5}{2}{P}_2,C_5\cup \frac{n-5}{2}{P}_2,\hfill & \text{if}n\text{is}\text{odd,}\hfill \end{array}$

where W is a bow, that is, two triangles $C_3$ having one common vertex.

A graph is said to be unicyclic if it contains exactly one cycle. The result of the second largest number of maximal independent sets among all connected unicyclic graphs are described in Theorems 2.11.

Theorem 2.11 ( [13] ) If U is a connected unicyclic graph of order $n\ge 6$ with $U\ne C_5$ and $Q\notin Q_1\left(n\right)$ , then $mi\left(G\right)\le u_2\left(n\right)$ , where

$u_2\left(n\right)=\{\begin{array}{ll}5r^{n-6}+1,\hfill & \text{if}n\text{is}\text{even,}\hfill \\ 3r^{n-5}+2,\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

Furthermore, $mi\left(G\right)=u_2\left(n\right)$ if and only if $U\in U_2\left(n\right)$ , where

$U_2\left(n\right)=\{\begin{array}{l}{Q}_{2e}^{\left(1\right)}\left(n\right),\text{if}n\text{is}\text{even},\\ U_{2o}^{\left(1\right)}\left(n\right),U_{2o}^{\left(2\right)}\left(n\right),U_{2o}^{\left(3\right)}\left(n\right),U_{2o}^{\left(4\right)}\left(n\right),U_{2o}^{\left(5\right)}\left(n\right),U_{2o}^{\left(6\right)}\left(n\right),\text{if}n\text{is}\text{odd},\end{array}$

where $U_{2o}^{\left(i\right)}\left(n\right)$ is shown in Figure 9.

3. Main Results

In this section, we determine the third largest values of $mi\left(G\right)$ among all quasi-tree graphs and quasi-forest graphs of order $n\ge 7$ , respectively. Moreover, the extremal graphs achieving these values are also determined.

Theorem 3.1 If Q is a quasi-tree graph of odd order $n\ge 7$ having $Q\notin Q_1\left(n\right)\mathrm{,}{Q}_2\left(n\right)$ , then $mi\left(Q\right)\le 3r^{n-5}+2$ . Furthermore, the equality holds if and only if $Q=U_{2o}^{\left(i\right)}$ , $1\le i\le 6$ , where $U_{2o}^{\left(i\right)}\left(n\right)$ is shown in Figure 9.

Proof. It is straightforward to check that $mi\left(U_{2o}^{\left(i\right)}\left(n\right)\right)=3r^{n-5}+2$ , $1\le i\le 6$ . Let Q be a quasi-tree graph of odd order $n\ge 7$ having $Q\notin Q_1\left(n\right)\mathrm{,}{Q}_2\left(n\right)$ such that $mi\left(Q\right)$ is as large as possible. Then $mi\left(Q\right)\ge 3r^{n-5}+2$ . If Q is a tree, by Theorems 2.1, 2.3 and $Q\notin Q_2\left(n\right)$ , we have that

$3r^{n-5}+2\le mi\left(Q\right)\le t_2\left(n\right)=3r^{n-5}+1$ . This is a contradiction.

Suppose that Q contains at least two cycles and x is the vertex such that $Q-x$ is a tree. Then ${{\displaystyle deg}}_Q\left(x\right)\ge 3$ . By Lemma 1.1, Theorems 2.1 and 2.2, $3r^{n-5}+2\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le r^{\left(n-1\right)-2}+1+r^{\left(n-4\right)-1}=3r^{n-5}+1$ , which is a contradiction. We obtain that Q is a connected unicyclic graph, thus the result follows from Theorem 2.11.

Theorem 3.2 If Q is a quasi-tree graph of even order $n\ge 8$ having $Q\notin Q_1\left(n\right)\mathrm{,}{Q}_2\left(n\right)$ , then $mi\left(Q\right)\le 5r^{n-6}$ . Furthermore, the equality holds if and only if $Q={\mathbb{Q}}^{\prime }\left(8\right)$ , ${\mathbb{Q}}^{″}\left(8\right)$ , ${\mathbb{Q}}^{‴}\left(10\right)$ , $Q_{3e}^{\left(i\right)}\left(n\right)$ , $1\le i\le 12$ , where ${\mathbb{Q}}^{\prime }\left(8\right)$ , ${\mathbb{Q}}^{″}\left(8\right)$ , ${\mathbb{Q}}^{‴}\left(10\right)$ and $Q_{3e}^{\left(i\right)}\left(n\right)$ are shown in Figure 10.

Proof. It is straightforward to check that $mi\left({\mathbb{Q}}^{\prime }\left(8\right)\right)=mi\left({\mathbb{Q}}^{″}\left(8\right)\right)=10$ , $mi\left({\mathbb{Q}}^{‴}\left(10\right)\right)=20$ and $mi\left(Q_{3e}^{\left(i\right)}\left(n\right)\right)=5r^{n-6}$ , $1\le i\le 12$ . Let Q be a quasi-tree graph of even order $n\ge 8$ having $Q\notin Q_1\left(n\right)\mathrm{,}{Q}_2\left(n\right)$ such that $mi\left(Q\right)$ is as large as possible. Then $mi\left(Q\right)\ge 5r^{n-6}$ . If Q is a tree, by Theorem 2.1, we have that $5r^{n-6}\le mi\left(Q\right)\le t_1\left(n\right)=r^{n-2}+1$ . This is a contradiction, so Q contains at least one cycle. Let x be the vertex such that $Q-x$ is a tree. Then x is on some cycle of Q, it follows that ${{\displaystyle deg}}_Q\left(x\right)\ge 2$ . In addition, by Lemma 1.1, Theorems 2.2 and 2.5, $mi\left(Q-x\right)\ge 5r^{n-6}-r^{\left(n-3\right)-1}=3r^{n-6}=t_3\left(n-1\right)$ . We consider the following three cases.

Case 1. $Q-x\in T_1\left(n-1\right)$ . If ${{\displaystyle deg}}_Q\left(x\right)\ge 6$ then $Q-N_Q\left[x\right]$ is a forest with at most $n-7$ vertices, by Lemma 1.1, Theorems 2.1 and 2.2, $5r^{n-6}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le r^{\left(n-1\right)-1}+r^{\left(n-7\right)-1}=9r^{n-8}$ . This is a contradiction. So we assume that $2\le {{\displaystyle deg}}_Q\left(x\right)\le 5$ .

• $\mathrm{deg}x=2$ . There are 6 possibilities for graph Q. See Figure 11. Note that $Q_1^{*}=Q_1\left(n\right)$ . By simple calculation, we have that $mi\left(Q_i^{\mathrm{<mo>\; *\; </mo>}}\right)\le r^{n-2}+1$ for $2\le i\le 6$ , a contradiction to $mi\left(Q\right)\ge 5r^{n-6}$ .

• $\mathrm{deg}x=3$ . Suppose that there exists an isolated vertex y in $Q-N_Q\left[x\right]$ and $Q-N_Q\left[x\right]-y\notin F_1\left(n-5\right)$ , then $mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)<r^{\left(n-1\right)-1}+r^{\left(n-4\right)-1-1}=5r^{n-6}$ . Hence there are 4 possibilities for graph Q. See Figure 12.

Note that $Q_8^{*}=Q_{2e}^{\left(2\right)}\left(n\right)$ , $Q_9^{*}=Q_{3e}^{\left(7\right)}\left(n\right)$ and $Q_{10}^{*}=Q_{1e}^{\left(2\right)}\left(n\right)$ . By simple calculation, we have $mi\left(Q_7^{*}\right)=r^{n-2}+1$ , a contradiction to $mi\left(Q\right)\ge 5r^{n-6}$ .

• $4\le degx\le 5$ . Since $Q-N_Q\left[x\right]$ is a forest of odd order $n-5$ or even or-

der $n-6$ , by Lemma 1.1, Theorems 2.1 and 2.2, we have $5r^{n-6}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le r^{n-2}+r^{n-6}=5r^{n-6}$ . The equalities holding imply that $Q-x=T_1\left(n-1\right)$ and $Q-N_Q\left[x\right]=F_1\left(n-5\right)$ or $F_1\left(n-6\right)$ . Hence we obtain that $Q=Q_{3e}^{\left(i\right)}\left(n\right)$ , $1\le i\le 4$ .

Case 2. $Q-x\in T_2\left(n-1\right)$ . If ${{\displaystyle deg}}_Q\left(x\right)\ge 4$ then $Q-N_Q\left[x\right]$ is a forest with at most $n-5$ vertices, by Lemma 1.1, Theorems 2.2 and 2.3, we have that $5r^{n-6}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le 3r^{\left(n-1\right)-5}+1+r^{\left(n-5\right)-1}=4r^{n-6}+1$ . This is a contradiction. So we assume that $2\le {{\displaystyle deg}}_Q\left(x\right)\le 3$ .

• $\mathrm{deg}x=2$ . Suppose that $Q-N_Q\left[x\right]\notin F_1\left(n-3\right)$ , by Lemma 1.1, Theorems 2.3 and 2.4, we have that

$5r^{n-6}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le 3r^{\left(n-1\right)-5}+1+7r^{\left(n-3\right)-7}=19r^{n-10}+1$ . The equalities holding imply that $n=10$ , that is, $Q-x=T_2\left(9\right)$ and $Q-N_Q\left[x\right]=F_2\left(7\right)$ . Hence we obtain that $Q={\mathbb{Q}}^{‴}\left(10\right)$ . Now we assume that $Q-N_Q\left[x\right]\in F_1\left(n-3\right)$ . There are 7 possibilities for graph Q. See Figure 13.

Note that $Q_{11}^{*}=Q_{2e}^{\left(1\right)}\left(n\right)$ , $Q_{12}^{*}=Q_{3e}^{\left(5\right)}\left(n\right)$ and $Q_{13}^{*}=Q_{3e}^{\left(6\right)}\left(n\right)$ . By simple calculation, we have $mi\left(Q_i^{\mathrm{<mo>\; *\; </mo>}}\right)\le r^{n-2}+2$ for $14\le i\le 17$ , a contradiction to $mi\left(Q\right)\ge 5r^{n-6}$ when $n\ge 10$ . In addition, $r^{8-2}+2=mi\left(Q_{17}^{*}\right)=5r^{8-6}$ when $n=8$ , it follows that $Q=Q_{3e}^{\left(6\right)}\left(8\right)$ .

• $\mathrm{deg}x=3$ . Suppose that $Q-N_Q\left[x\right]\notin F_1\left(n-4\right)$ , by Lemma 1.1, Theorems 2.3 and 2.4, we have that $5r^{n-6}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le 3r^{\left(n-1\right)-5}+1+3r^{\left(n-4\right)-4}=9r^{n-8}+1$ . The equalities holding imply that $n=8$ , that is, $Q-x=T_2\left(7\right)$ and $Q-N_Q\left[x\right]=F_2\left(4\right)$ . Hence we obtain that $Q={\mathbb{Q}}^{\prime }\left(8\right),{\mathbb{Q}}^{″}\left(8\right)$ . Now we assume that $Q-N_Q\left[x\right]\in F_1\left(n-4\right)$ . Since $Q-x\in T_2\left(n-1\right)$ and $Q-N_Q\left[x\right]\in F_1\left(n-4\right)$ , it follows that $Q=Q_{2e}^{\left(i\right)}\left(n\right)$ , $2\le i\le 4$ , a contradiction to $Q\notin Q_2\left(n\right)$ .

Case 3. $Q-x\in T_3\left(n-1\right)$ . Since $Q-N_Q\left[x\right]$ is a forest with at most $n-3$ vertices, by Lemma 1.1, Theorems 2.2 and 2.5, we have $5r^{n-6}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le 3r^{\left(n-1\right)-5}+r^{\left(n-3\right)-1}=5r^{n-6}$ . The equalities holding imply that $Q-x\in T_3\left(n-1\right)$ and $Q-N_Q\left[x\right]\in F_1\left(n-3\right)$ or $F_1\left(n-4\right)$ . For the case that $Q-N_Q\left[x\right]\in F_1\left(n-4\right)$ , we obtain that $Q=Q_{3e}^{\left(i\right)}$ , $7\le i\le 9$ . For the other case that $Q-N_Q\left[x\right]\in F_1\left(n-3\right)$ There are 7 possibilities for graph Q. See Figure 14.

Note that $Q_{18}^{*}=Q_{3e}^{\left(10\right)}\left(n\right)$ , $Q_{19}^{*}=Q_{3e}^{\left(11\right)}\left(n\right)$ and $Q_{20}^{*}=Q_{3e}^{\left(12\right)}\left(n\right)$ . By simple calculation, we have $mi\left(Q_i^{\mathrm{<mo>\; *\; </mo>}}\right)\le r^{n-2}+1$ for $21\le i\le 24$ , a contradiction to $mi\left(Q\right)\ge 5r^{n-6}$ .

In the following, we will investigate the same problem for quasi-forest graphs.

Theorem 3.3 If Q is a quasi-forest graph of odd order $n\ge 7$ having $Q\notin {\bar{Q}}_1\left(n\right)\mathrm{,}{\bar{Q}}_2\left(n\right)$ , then $mi\left(Q\right)\le 9r^{n-7}$ . Furthermore, the equality holds if and only if $Q={\bar{Q}}_{3o}^{\left(i\right)}\left(n\right)$ , $1\le i\le 4$ , where ${\bar{Q}}_{3o}^{\left(i\right)}\left(n\right)$ is shown in Figure 15.

Proof. It is straightforward to check that $mi\left({\bar{Q}}_{3o}^{\left(i\right)}\left(n\right)\right)=9r^{n-7}$ , $1\le i\le 4$ . Let Q be a quasi-forest graph of odd order $n\ge 7$ having $Q\notin {\bar{Q}}_1\left(n\right)\mathrm{,}{\bar{Q}}_2\left(n\right)$ such that $mi\left(Q\right)$ is as large as possible. Then $mi\left(Q\right)\ge 9r^{n-7}$ . If Q is a forest, by Theorem 2.2, we have that $9r^{n-7}\le mi\left(Q\right)\le f_1\left(n\right)=r^{n-1}$ . This is a contradiction, so Q contains at least one cycle. Let x be a vertex such that $Q-x$ is a forest. Then x is on some cycle of Q, it follows that ${{\displaystyle deg}}_Q\left(x\right)\ge 2$ and $Q-N_Q\left[x\right]$ is a forest with at most $n-3$ vertices. By Lemma 1.1, Theorem2.2 and 2.6, we obtain that $mi\left(Q-x\right)\ge mi\left(Q\right)-mi\left(Q-N_Q\left[x\right]\right)\ge 9r^{n-7}-r^{n-3}=5r^{n-7}=f_3\left(n-1\right)$ . We consider the following three ases.

Case 1. $Q-x\in F_1\left(n-1\right)$ . If ${{\displaystyle deg}}_Q\left(x\right)\ge 7$ then $Q-N_Q\left[x\right]$ is a forest with at most $n-8$ vertices, by Lemma 1.1 and Theorem 2.2, we have that $9r^{n-7}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le r^{n-1}+r^{\left(n-8\right)-1}=17r^{n-9}$ . This is a con- tradiction. So we assume that $2\le {{\displaystyle deg}}_Q\left(x\right)\le 6$ . There are 9 possibilities for graph Q. See Figure 16.

Note that ${\bar{Q}}_1^{\mathrm{<mo>\; *\; </mo>}}\in {\bar{Q}}_1\left(n\right)$ , ${\bar{Q}}_2^{\mathrm{<mo>\; *\; </mo>}}\in {\bar{Q}}_2\left(n\right)$ , ${\bar{Q}}_3^{\mathrm{<mo>\; *\; </mo>}}\in {\bar{Q}}_3\left(n\right)$ , ${\bar{Q}}_4^{*}={\bar{Q}}_{3o}^{\left(1\right)}\left(n\right)$ , ${\bar{Q}}_5^{*}={\bar{Q}}_{3o}^{\left(2\right)}\left(n\right)$ , ${\bar{Q}}_7^{*}={\bar{Q}}_{3o}^{\left(3\right)}\left(n\right)$ . By simple calculation, we have $mi\left({\bar{Q}}_i^{*}\right)\le 17r^{n-9}$ , $i=6,8,9$ , a contradiction to $mi\left(Q\right)\ge 9r^{n-7}$ .

Case 2. $Q-x=F_2\left(n-1\right)$ . If ${{\displaystyle deg}}_Q\left(x\right)\ge 3$ then $Q-N_Q\left[x\right]$ is a forest with at most $n-4$ vertices, by Lemma 1.1, Theorems 2.2 and 2.4, we have that $9r^{n-7}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le 3r^{\left(n-1\right)-4}+r^{\left(n-4\right)-1}=4r^{n-5}$ . This is a contradiction. So we assume that ${{\displaystyle \mathrm{deg}}}_Q\left(x\right)=2$ . There are 5 possibilities for graph Q. See Figure 17.

Note that ${\bar{Q}}_{10}^{*}={\bar{Q}}_2\left(n\right)$ , ${\bar{Q}}_{12}^{*}={\bar{Q}}_2\left(n\right)$ , ${\bar{Q}}_{14}^{*}={\bar{Q}}_{3o}^{\left(4\right)}\left(n\right)$ . By simple calculation, we have $mi\left({\bar{Q}}_i^{\mathrm{<mo>\; *\; </mo>}}\right)\le 3r^{n-5}+1$ , $i=11,13$ , a contradiction to $mi\left(Q\right)\ge 9r^{n-7}$ .

Case 3. $Q-x\in F_3\left(n-1\right)$ . Since $Q-N_Q\left[x\right]$ is a forest with at most $n-3$ vertices, by Lemma 1.1, Theorems 2.2 and 2.6, we have that

$9r^{n-7}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le 5r^{\left(n-1\right)-6}+r^{n-3}=9r^{n-7}$ . The equali-

ties holding imply that $Q-x\in F_3\left(n-1\right)$ and $Q-N_Q\left[x\right]\in F_1\left(n-3\right)$ . There are 3 possibilities for graph Q. See Figure 18.

Note that ${\bar{Q}}_{17}^{*}={\bar{Q}}_{3o}^{\left(1\right)}\left(n\right)$ . By simple calculation, we have $mi\left({\bar{Q}}_i^{*}\right)=8r^{n-7}$ , $15\le i\le 16$ , a contradiction to $mi\left(Q\right)\ge 9r^{n-7}$ .

Theorem 3.4 If Q is a quasi-forest graph of even order $n\ge 8$ having $Q\notin {\bar{Q}}_1\left(n\right)\mathrm{,}{\bar{Q}}_2\left(n\right)$ , then $mi\left(Q\right)\le 11r^{n-8}$ . Furthermore, the equality holds if and

only if $Q=Q_2\left(8\right)\cup \frac{n-8}{2}{P}_2$ .

Proof. It is straightforward to check that $mi\left(Q_2\left(8\right)\cup \frac{n-8}{2}{P}_2\right)=11r^{n-8}$ . Let Q

be a quasi-forest graph of even order $n\ge 8$ having $Q\notin {\bar{Q}}_1\left(n\right)\mathrm{,}{\bar{Q}}_2\left(n\right)$ such that $mi\left(Q\right)$ is as large as possible. Then $mi\left(Q\right)\ge 11r^{n-8}$ . If Q is a forest, by Theorems 2.2, 2.4, 2.6, 2.8 and 2.10, we have that $11r^{n-8}\le mi\left(Q\right)\le f_3\left(n\right)=5r^{n-6}$ . This is a contradiction, so Q contains a coponent $\hat{Q}$ with at least one cycle.

Let $\left|\hat{Q}\right|=s$ . Suppose that $Q-\hat{Q}\ne \frac{n-s}{2}{P}_2$ . Since $\hat{Q}$ is not a tree and $Q\notin {\bar{Q}}_1\left(n\right)\mathrm{,}{\bar{Q}}_2\left(n\right)$ , by Lemma 1.2, Theorems 2.2, 2.4 and 2.7, we have that

$\begin{array}{l}mi\left(Q\right)=mi\left(\hat{Q}\right)\cdot mi\left(Q-\hat{Q}\right)\\ \le \{\begin{array}{ll}3r^{s-4}\cdot 3r^{\left(n-s\right)-4},\hfill & \text{if}s\ge 4\text{is}\text{even},\hfill \\ 3\cdot 7r^{\left(n-3\right)-7},\hfill & \text{if}s=3,\hfill \\ \left(r^{s-1}+1\right)\cdot r^{\left(n-s\right)-1},\hfill & \text{if}s\ge 5\text{is}\text{odd},\hfill \end{array}\\ \le \{\begin{array}{ll}9r^{n-8},\hfill & \text{if}s\ge 4\text{is}\text{even},\hfill \\ 21r^{n-10},\hfill & \text{if}s=3,\hfill \\ 5r^{n-6},\hfill & \text{if}s\ge 5\text{is}\text{odd},\hfill \end{array}\\ <11r^{n-8},\end{array}$

which is a contradiction. Hence we obtain that s is even and $Q-\hat{Q}=\frac{n-s}{2}{P}_2$ .

Let x be the vertex in $\hat{Q}$ such that $\hat{Q}-x$ is a forest and $w\left(\hat{Q}-x\right)$ be the number of components of $\hat{Q}-x$ . We consider the following two cases.

Case 1. $w\left(\hat{Q}-x\right)=1$ . Then $\hat{Q}$ is a quasi-tree graph. Since

$Q\notin {\bar{Q}}_1\left(n\right)\mathrm{,}{\bar{Q}}_2\left(n\right)$ it follows that $s\ge 8$ . By Lemma 1.2 and Theorem 2.9, it follows that $mi\left(Q\right)=\left(5r^{s-6}+1\right)\cdot r^{n-s}=5r^{n-6}+r^{n-s}\le 11r^{n-8}$ . The equality holding

imply that $s=8$ . In conclusion, $Q=Q_2\left(8\right)\cup \frac{n-8}{2}{P}_2$ .

Case 2. $w\left(\hat{Q}-x\right)\ge 2$ . Then $degx\ge 3$ . In addition, suppose that $Q-N_Q\left[x\right]$ has a isolated vertex or ${{\displaystyle deg}}_Q\left(x\right)\ge 4$ , by Lemma 1.1 and Theorem 2.2, we have that $11r^{n-8}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le r^{\left(n-1\right)-1}+r^{\left(n-5\right)-1}=5r^{n-6}$ . This is a contradiction, hence, we have that ${{\displaystyle deg}}_Q\left(x\right)=3$ and $Q-N_Q\left[x\right]$ has no isolated vertex. For the case that $Q-x\notin F_1\left(n-1\right)$ , by Lemma 1.1, Theorems 2.2 and 2.4, we have that $11r^{n-8}\le mi\left(Q\right)\le mi\left(Q-x\right)+mi\left(Q-N_Q\left[x\right]\right)\le 7r^{\left(n-1\right)-7}+r^{n-4}=11r^{n-8}$ . The equa- lities holding imply that $Q-x\in F_2\left(n-1\right)$ and $Q-N_Q\left[x\right]\in F_1\left(n-4\right)$ . Since $w\left(\hat{Q}-x\right)\ge 2$ , there no such graph Q. For the other case that $Q-x\in F_1\left(n-1\right)$ , there are 2 possibilities for graph Q. See Figure 19.