The Number of Maximal Independent Sets in Quasi-Tree Graphs and Quasi-Forest Graphs

Jenq-Jong Lin, Min-Jen Jou

Ling Tung University, Taichung City.

DOI: 10.4236/ojdm.2017.73013                

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(G) is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex x ∈V(G) 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

Figure 1. The baton $B\left(i\mathrm{,}j\right)$ with $j=j_1+j_2$ .

Figure 2. The trees $T_2\left(n\right)$ .

Figure 3. The trees ${T^{\prime }}_2\left(8\right)$ and ${T^{″}}_2\left(8\right)$ .

$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}$

Figure 4. The trees $T_3\left(8\right)\mathrm{,}{T^{\prime }}_3\left(10\right)$ and ${T^{″}}_3\left(10\right)$ .

Figure 5. The trees $T_3\left(n\right)$ .

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}$

Figure 6. The graph $Q_1\left(n\right)$ .

Figure 7. The graphs $Q_{2e}^{\left(i\right)}\left(n\right)$ , $1\le i\le 4$ .

Figure 8. The graphs $Q_{2o}^{\left(i\right)}\left(7\right)$ , $1\le i\le 4$ .

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

Figure 9. The graphs $U_{2o}^{\left(i\right)}\left(n\right)$ , $1\le i\le 6$ .

$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-

Figure 10. The graphs ${\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)$ , $1\le i\le 12$ .

Figure 11. The graphs $Q_i^{\mathrm{<mo>\; *\; </mo>}}$ , $1\le i\le 6$ .

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

Figure 12. The graphs $Q_i^{\mathrm{<mo>\; *\; </mo>}}$ , $7\le i\le 10$ .

$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.

Figure 13. The graphs $Q_i^{\mathrm{<mo>\; *\; </mo>}}$ , $11\le i\le 17$ .

Figure 14. The graphs $Q_i^{\mathrm{<mo>\; *\; </mo>}}$ , $18\le i\le 24$ .

Figure 15. The graphs ${\bar{Q}}_{3o}^{\left(i\right)}\left(n\right)$ , $1\le i\le 4$ .

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-

Figure 16. The graphs ${\bar{Q}}_i^{\mathrm{<mo>\; *\; </mo>}}$ , $1\le i\le 9$ .

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}$

Figure 17. The graphs ${\bar{Q}}_i^{\mathrm{<mo>\; *\; </mo>}}$ , $10\le i\le 14$ .

Figure 18. The graphs ${\bar{Q}}_i^{\mathrm{<mo>\; *\; </mo>}}$ , $15\le i\le 17$ .

Figure 19. The graphs ${\bar{Q}}_i^{\mathrm{<mo>\; *\; </mo>}}$ , $18\le i\le 19$ .

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.

Note that ${\bar{Q}}_{18}^{*}={\bar{Q}}_2\left(n\right)$ and ${\bar{Q}}_{19}^{*}=Q_{2e}^{\left(1\right)}\left(8\right)\cup \frac{n-8}{2}{P}_2$ when $s=8$ . On the other hand, $mi\left({\bar{Q}}_{19}^{\mathrm{<mo>\; *\; </mo>}}\right)\le 21r^{n-10}$ when $s\ge 10$ , a contradiction to $mi\left(Q\right)\ge 11r^{n-8}$ .

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Moon, J.W. and Moser, L. (1965) On Cliques in Graphs. Israel Journal of Mathematics, 3, 23-28. https://doi.org/10.1007/BF02760024
[2]	Jou, M.J. and Chang, G.J. (1995) Survey on Conunting Maximal Independent Sets. In: Tangmance, S. and Schulz, E., Eds., Proceedings of the Second Asian Mathema-tical Conference, World Scientific, Singapore, 265-275.
[3]	Jin, Z. and Li, X. (2008) Graphs with the Second Largest Number of Maximal Independent Sets. Discrete Mathematics, 308, 5864-5870. https://doi.org/10.1016/j.disc.2007.10.032
[4]	Jou, M.J. and Lin, J.J. (2009) Trees with the Second Largest Number of Maximal Independent Sets. Discrete Mathematics, 309, 4469-4474. https://doi.org/10.1016/j.disc.2009.02.007
[5]	Jin, Z. and Yan, H.F. (2009) Trees with the Second and Third Largest Number of Maximal Independent Sets. Ars Combinatoria, 93, 341-351.
[6]	Liu, H. and Lu, M. (2008) On the Spectral Radius of Quasi-Tree Graphs. Linear Algebra and Its Applications, 428, 2708-2714. https://doi.org/10.1016/j.laa.2007.12.017
[7]	Lin, J.J. (2010) Quasi-Tree Graphs with the Largest Number of Maximal Independent Sets. Ars Combinatoria, 97, 27-32.
[8]	Lin, J.J. (2013) Quasi-Tree Graphs with the Second Largest Number of Maximal Independent Sets. Ars Combinatoria, 108, 257-267.
[9]	Sagan, B.E. and Vatter, V.R. (2006) Maximal and Maximum Independent Sets in Graphs with at Most Cycles. Journal of Graph Theory, 53, 283-314. https://doi.org/10.1002/jgt.20186
[10]	Jou, M.J. (1991) The Number of Maximal Independent Sets in Graphs. Master Thesis, Department of Mathematics, National Central University, Taiwan.
[11]	Jou, M.J. and Chang, G.J. (1997) Maximal Independent Sets in Graphs with at Most One Cycle. Discrete Applied Mathematics, 79, 67-73. https://doi.org/10.1016/S0166-218X(97)00033-4
[12]	Jou, M.J. and Lin, J.J. (2010) Forests with the Third Largest Number of Maximal Independent Sets. Ling Tung Journal, 27, 203-212.
[13]	Lin, J.J. and Jou, M.J. The Numbers of Maximal Independent Sets in Connected Unicyclic Graphs. Utilitas Math., to Appear.