Back
 OJDM  Vol.7 No.3 , July 2017
The Number of Maximal Independent Sets in Quasi-Tree Graphs and Quasi-Forest Graphs
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.

1. Introduction and Preliminary

Let G = ( V , E ) 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 MI ( G ) and its cardinality by m i ( G ) .

The problem of determining the largest value of m i ( G ) 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 m i ( G ) 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 m i ( G ) among all trees of order n. 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). 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 m i ( G ) 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 = ( V , E ) , the neighborhood N G ( x ) of a vertex x is the set of vertices adjacent to x in G and the closed neighborhood N G [ x ] is { x } N G ( x ) . The degree of x is the cardinality of N G ( x ) , denoted by d e g G ( x ) . For a set A V ( G ) , 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 ( G 1 ) V ( G 2 ) = . The union of two disjoint graphs G 1 and G 2 is the graph G 1 G 2 with vertex set V ( G 1 G 2 ) = V ( G 1 ) V ( G 2 ) and edge set E ( G 1 G 2 ) = E ( G 1 ) E ( G 2 ) . n G 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 = 2 .

Lemma 1.1 ( [9] ) For any vertex x in a graph G, m i ( G ) m i ( G x ) + m i ( G N G [ x ] ) .

Lemma 1.2 ( [10] ) If G is the union of two disjoint graphs G 1 and G 2 , then m i ( G ) = m i ( G 1 ) m i ( G 2 ) .

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 1 vertices, then m i ( T ) t 1 ( n ) , where

t 1 ( n ) = { r n 2 + 1 , if n is even, r n 1 , if n is odd .

Furthermore, m i ( T ) = t 1 ( n ) if and only if T T 1 ( n ) , where

T 1 ( n ) = { B ( 2 , n 2 2 ) or B ( 4 , n 4 2 ) , if n is even, B ( 1 , n 1 2 ) , if n is odd,

where B ( i , j ) is the set of batons, which are the graphs obtained from the basic path P of i 1 vertices by attaching j 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 1 vertices, then m i ( F ) f 1 ( n ) , where

f 1 ( n ) = { r n , if n is even, r n 1 , if n is odd .

Furthermore, m i ( F ) = f 1 ( n ) if and only if F F 1 ( n ) , where

F 1 ( n ) = { n 2 P 2 , if n is even, B ( 1 ; n 1 2 s 2 ) s P 2 for some s with 0 s n 1 2 , if n is odd .

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 4 vertices having T T 1 ( n ) , then m i ( T ) t 2 ( n ) , where

t 2 ( n ) = { r n 2 , if n 4 is even , 3 , if n = 5 , 3 r n 5 + 1 , if n 7 is odd .

Furthermore, m i ( T ) = t 2 ( n ) if and only if T = T 2 ( 8 ) , T 2 ( 8 ) , P 10 or T T 2 ( n ) , where T 2 ( n ) and T 2 ( 8 ) , T 2 ( 8 ) are shown in Figure 2 and Figure 3, respectively.

Theorem 2.4 ( [4] ) If F is a forest with n 4 vertices having F F 1 ( n ) , then m i ( F ) f 2 ( n ) , where

Figure 1. The baton B ( i , j ) with j = j 1 + j 2 .

Figure 2. The trees T 2 ( n ) .

Figure 3. The trees T 2 ( 8 ) and T 2 ( 8 ) .

f 2 ( n ) = { 3 r n 4 , if n 4 is even , 3 , if n = 5 , 7 r n 7 , if n 7 is odd .

Furthermore, m i ( F ) = f 2 ( n ) if and only if F F 2 ( n ) , where

F 2 ( n ) = { P 4 n 4 2 P 2 , if n 4 is even , T 2 ( 5 ) or P 4 P 1 , if n = 5 , P 7 n 7 2 P 2 , if n 7 is odd .

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 7 vertices having T T i ( n ) , i = 1 , 2 , then m i ( T ) t 3 ( n ) , where

t 3 ( n ) = { 3 r n 5 , if n 7 is odd , 7 , if n = 8 , 15 , if n = 10 , 7 r n 8 + 2 , if n 12 is even .

Furthermore, m i ( T ) = t 3 ( n ) if and only if T = T 3 ( 8 ) , T 3 ( 10 ) , T 3 ( 10 ) or T T 3 ( n ) , where T 3 ( 8 ) , T 3 ( 10 ) , T 3 ( 10 ) , T 3 ( n ) are shown in Figure 4 and Figure 5, respectively.

Theorem 2.6 ( [12] ) If F is a forest with n 8 vertices having F F i ( n ) , i = 1 , 2 , then m i ( F ) f 3 ( n ) , where

f 3 ( n ) = { 5 r n 6 , if n is even, 13 r n 9 , if n is odd .

Furthermore, m i ( F ) = f 3 ( n ) if and only if F F 3 ( n ) , where

F 3 ( n ) = { T 1 ( 6 ) n 6 2 P 2 , if n is even, T 2 ( 9 ) n 9 2 P 2 , if n is odd .

Figure 4. The trees T 3 ( 8 ) , T 3 ( 10 ) and T 3 ( 10 ) .

Figure 5. The trees T 3 ( n ) .

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 5 vertices, then m i ( Q ) q 1 ( n ) , where

q 1 ( n ) = { 3 r n 4 , if n is even, r n 1 + 1 , if n is odd .

Furthermore, m i ( Q ) = q 1 ( n ) if and only if Q = C 5 or Q Q 1 ( n ) , where Q 1 ( n ) is shown in Figure 6.

Theorem 2.8 ( [7] )If Q is a quasi-forest graph with n 2 vertices, then m i ( Q ) q ¯ 1 ( n ) , where

q ¯ 1 ( n ) = { r n , if n is even, 3 r n 3 , if n is odd .

Furthermore, m i ( Q ) = q ¯ 1 ( n ) if and only if Q Q ¯ 1 ( n ) , where

Q ¯ 1 ( n ) = { n 2 P 2 , if n is even, C 3 n 3 2 P 2 , if n is odd .

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 6 vertices having Q Q 1 ( n ) , then m i ( Q ) q 2 ( n ) , where

q 2 ( n ) = { 5 r n 6 + 1 , if n is even, r n 1 , if n is odd .

Furthermore, m i ( Q ) = q 2 ( n ) if and only if Q Q 2 ( n ) , where

Q 2 ( n ) = { Q 2 e ( 1 ) ( n ) , Q 2 e ( 2 ) ( n ) , Q 2 e ( 3 ) ( n ) , Q 2 e ( 4 ) ( n ) , if n is even, B ( 1 , n 1 2 ) , Q 2 o ( 1 ) ( 7 ) , Q 2 o ( 2 ) ( 7 ) , Q 2 o ( 3 ) ( 7 ) , Q 2 o ( 4 ) ( 7 ) , if n is odd,

where Q 2 ( n ) is shown in Figure 7 and Figure 8.

Theorem 2.10 ( [8] )If Q is a quasi-forest graph with n 4 vertices having Q Q ¯ 1 ( n ) , then m i ( Q ) q ¯ 2 ( n ) , where

q ¯ 2 ( n ) = { 3 r n 4 , if n is even, 5 r n 5 , if n is odd .

Figure 6. The graph Q 1 ( n ) .

Figure 7. The graphs Q 2 e ( i ) ( n ) , 1 i 4 .

Figure 8. The graphs Q 2 o ( i ) ( 7 ) , 1 i 4 .

Furthermore, m i ( Q ) = q ¯ 2 ( n ) if and only if Q Q ¯ 2 ( n ) , where

Q ¯ 2 ( n ) = { P 4 n 4 2 P 2 , Q 1 ( n 2 s ) s P 2 , Q 2 ( 6 ) n 6 2 P 2 , C 3 B ( 1 , n 4 2 s 2 ) s P 2 , if n is even, Q 1 ( 5 ) n 5 2 P 2 , W n 5 2 P 2 , C 5 n 5 2 P 2 , if n is odd,

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 6 with U C 5 and Q Q 1 ( n ) , then m i ( G ) u 2 ( n ) , where

u 2 ( n ) = { 5 r n 6 + 1 , if n is even, 3 r n 5 + 2 , if n is odd .

Furthermore, m i ( G ) = u 2 ( n ) if and only if U U 2 ( n ) , where

U 2 ( n ) = { Q 2 e ( 1 ) ( n ) , if n is even , U 2 o ( 1 ) ( n ) , U 2 o ( 2 ) ( n ) , U 2 o ( 3 ) ( n ) , U 2 o ( 4 ) ( n ) , U 2 o ( 5 ) ( n ) , U 2 o ( 6 ) ( n ) , if n is odd ,

where U 2 o ( i ) ( n ) is shown in Figure 9.

3. Main Results

In this section, we determine the third largest values of m i ( G ) among all quasi-tree graphs and quasi-forest graphs of order n 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 7 having Q Q 1 ( n ) , Q 2 ( n ) , then m i ( Q ) 3 r n 5 + 2 . Furthermore, the equality holds if and only if Q = U 2 o ( i ) , 1 i 6 , where U 2 o ( i ) ( n ) is shown in Figure 9.

Proof. It is straightforward to check that m i ( U 2 o ( i ) ( n ) ) = 3 r n 5 + 2 , 1 i 6 . Let Q be a quasi-tree graph of odd order n 7 having Q Q 1 ( n ) , Q 2 ( n ) such that m i ( Q ) is as large as possible. Then m i ( Q ) 3 r n 5 + 2 . If Q is a tree, by Theorems 2.1, 2.3 and Q Q 2 ( n ) , we have that

Figure 9. The graphs U 2 o ( i ) ( n ) , 1 i 6 .

3 r n 5 + 2 m i ( Q ) t 2 ( n ) = 3 r 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 d e g Q ( x ) 3 . By Lemma 1.1, Theorems 2.1 and 2.2, 3 r n 5 + 2 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) r ( n 1 ) 2 + 1 + r ( n 4 ) 1 = 3 r 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 8 having Q Q 1 ( n ) , Q 2 ( n ) , then m i ( Q ) 5 r n 6 . Furthermore, the equality holds if and only if Q = ( 8 ) , ( 8 ) , ( 10 ) , Q 3 e ( i ) ( n ) , 1 i 12 , where ( 8 ) , ( 8 ) , ( 10 ) and Q 3 e ( i ) ( n ) are shown in Figure 10.

Proof. It is straightforward to check that m i ( ( 8 ) ) = m i ( ( 8 ) ) = 10 , m i ( ( 10 ) ) = 20 and m i ( Q 3 e ( i ) ( n ) ) = 5 r n 6 , 1 i 12 . Let Q be a quasi-tree graph of even order n 8 having Q Q 1 ( n ) , Q 2 ( n ) such that m i ( Q ) is as large as possible. Then m i ( Q ) 5 r n 6 . If Q is a tree, by Theorem 2.1, we have that 5 r n 6 m i ( Q ) t 1 ( n ) = 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 d e g Q ( x ) 2 . In addition, by Lemma 1.1, Theorems 2.2 and 2.5, m i ( Q x ) 5 r n 6 r ( n 3 ) 1 = 3 r n 6 = t 3 ( n 1 ) . We consider the following three cases.

Case 1. Q x T 1 ( n 1 ) . If d e g Q ( x ) 6 then Q N Q [ x ] is a forest with at most n 7 vertices, by Lemma 1.1, Theorems 2.1 and 2.2, 5 r n 6 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) r ( n 1 ) 1 + r ( n 7 ) 1 = 9 r n 8 . This is a contradiction. So we assume that 2 d e g Q ( x ) 5 .

deg x = 2 . There are 6 possibilities for graph Q. See Figure 11. Note that Q 1 * = Q 1 ( n ) . By simple calculation, we have that m i ( Q i * ) r n 2 + 1 for 2 i 6 , a contradiction to m i ( Q ) 5 r n 6 .

deg x = 3 . Suppose that there exists an isolated vertex y in Q N Q [ x ] and Q N Q [ x ] y F 1 ( n 5 ) , then m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) < r ( n 1 ) 1 + r ( n 4 ) 1 1 = 5 r n 6 . Hence there are 4 possibilities for graph Q. See Figure 12.

Note that Q 8 * = Q 2 e ( 2 ) ( n ) , Q 9 * = Q 3 e ( 7 ) ( n ) and Q 10 * = Q 1 e ( 2 ) ( n ) . By simple calculation, we have m i ( Q 7 * ) = r n 2 + 1 , a contradiction to m i ( Q ) 5 r n 6 .

4 d e g x 5 . Since Q N Q [ x ] is a forest of odd order n 5 or even or-

Figure 10. The graphs ( 8 ) , ( 8 ) , ( 10 ) and Q 3 e ( i ) ( n ) , 1 i 12 .

Figure 11. The graphs Q i * , 1 i 6 .

der n 6 , by Lemma 1.1, Theorems 2.1 and 2.2, we have 5 r n 6 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) r n 2 + r n 6 = 5 r n 6 . The equalities holding imply that Q x = T 1 ( n 1 ) and Q N Q [ x ] = F 1 ( n 5 ) or F 1 ( n 6 ) . Hence we obtain that Q = Q 3 e ( i ) ( n ) , 1 i 4 .

Case 2. Q x T 2 ( n 1 ) . If d e g Q ( x ) 4 then Q N Q [ x ] is a forest with at most n 5 vertices, by Lemma 1.1, Theorems 2.2 and 2.3, we have that 5 r n 6 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) 3 r ( n 1 ) 5 + 1 + r ( n 5 ) 1 = 4 r n 6 + 1 . This is a contradiction. So we assume that 2 d e g Q ( x ) 3 .

deg x = 2 . Suppose that Q N Q [ x ] F 1 ( n 3 ) , by Lemma 1.1, Theorems 2.3 and 2.4, we have that

Figure 12. The graphs Q i * , 7 i 10 .

5 r n 6 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) 3 r ( n 1 ) 5 + 1 + 7 r ( n 3 ) 7 = 19 r n 10 + 1 . The equalities holding imply that n = 10 , that is, Q x = T 2 ( 9 ) and Q N Q [ x ] = F 2 ( 7 ) . Hence we obtain that Q = ( 10 ) . Now we assume that Q N Q [ x ] F 1 ( n 3 ) . There are 7 possibilities for graph Q. See Figure 13.

Note that Q 11 * = Q 2 e ( 1 ) ( n ) , Q 12 * = Q 3 e ( 5 ) ( n ) and Q 13 * = Q 3 e ( 6 ) ( n ) . By simple calculation, we have m i ( Q i * ) r n 2 + 2 for 14 i 17 , a contradiction to m i ( Q ) 5 r n 6 when n 10 . In addition, r 8 2 + 2 = m i ( Q 17 * ) = 5 r 8 6 when n = 8 , it follows that Q = Q 3 e ( 6 ) ( 8 ) .

deg x = 3 . Suppose that Q N Q [ x ] F 1 ( n 4 ) , by Lemma 1.1, Theorems 2.3 and 2.4, we have that 5 r n 6 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) 3 r ( n 1 ) 5 + 1 + 3 r ( n 4 ) 4 = 9 r n 8 + 1 . The equalities holding imply that n = 8 , that is, Q x = T 2 ( 7 ) and Q N Q [ x ] = F 2 ( 4 ) . Hence we obtain that Q = ( 8 ) , ( 8 ) . Now we assume that Q N Q [ x ] F 1 ( n 4 ) . Since Q x T 2 ( n 1 ) and Q N Q [ x ] F 1 ( n 4 ) , it follows that Q = Q 2 e ( i ) ( n ) , 2 i 4 , a contradiction to Q Q 2 ( n ) .

Case 3. Q x T 3 ( n 1 ) . Since Q N Q [ x ] is a forest with at most n 3 vertices, by Lemma 1.1, Theorems 2.2 and 2.5, we have 5 r n 6 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) 3 r ( n 1 ) 5 + r ( n 3 ) 1 = 5 r n 6 . The equalities holding imply that Q x T 3 ( n 1 ) and Q N Q [ x ] F 1 ( n 3 ) or F 1 ( n 4 ) . For the case that Q N Q [ x ] F 1 ( n 4 ) , we obtain that Q = Q 3 e ( i ) , 7 i 9 . For the other case that Q N Q [ x ] F 1 ( n 3 ) There are 7 possibilities for graph Q. See Figure 14.

Note that Q 18 * = Q 3 e ( 10 ) ( n ) , Q 19 * = Q 3 e ( 11 ) ( n ) and Q 20 * = Q 3 e ( 12 ) ( n ) . By simple calculation, we have m i ( Q i * ) r n 2 + 1 for 21 i 24 , a contradiction to m i ( Q ) 5 r 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 7 having Q Q ¯ 1 ( n ) , Q ¯ 2 ( n ) , then m i ( Q ) 9 r n 7 . Furthermore, the equality holds if and only if Q = Q ¯ 3 o ( i ) ( n ) , 1 i 4 , where Q ¯ 3 o ( i ) ( n ) is shown in Figure 15.

Figure 13. The graphs Q i * , 11 i 17 .

Figure 14. The graphs Q i * , 18 i 24 .

Figure 15. The graphs Q ¯ 3 o ( i ) ( n ) , 1 i 4 .

Proof. It is straightforward to check that m i ( Q ¯ 3 o ( i ) ( n ) ) = 9 r n 7 , 1 i 4 . Let Q be a quasi-forest graph of odd order n 7 having Q Q ¯ 1 ( n ) , Q ¯ 2 ( n ) such that m i ( Q ) is as large as possible. Then m i ( Q ) 9 r n 7 . If Q is a forest, by Theorem 2.2, we have that 9 r n 7 m i ( Q ) f 1 ( n ) = 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 d e g Q ( x ) 2 and Q N Q [ x ] is a forest with at most n 3 vertices. By Lemma 1.1, Theorem2.2 and 2.6, we obtain that m i ( Q x ) m i ( Q ) m i ( Q N Q [ x ] ) 9 r n 7 r n 3 = 5 r n 7 = f 3 ( n 1 ) . We consider the following three ases.

Case 1. Q x F 1 ( n 1 ) . If d e g Q ( x ) 7 then Q N Q [ x ] is a forest with at most n 8 vertices, by Lemma 1.1 and Theorem 2.2, we have that 9 r n 7 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) r n 1 + r ( n 8 ) 1 = 17 r n 9 . This is a con- tradiction. So we assume that 2 d e g Q ( x ) 6 . There are 9 possibilities for graph Q. See Figure 16.

Note that Q ¯ 1 * Q ¯ 1 ( n ) , Q ¯ 2 * Q ¯ 2 ( n ) , Q ¯ 3 * Q ¯ 3 ( n ) , Q ¯ 4 * = Q ¯ 3 o ( 1 ) ( n ) , Q ¯ 5 * = Q ¯ 3 o ( 2 ) ( n ) , Q ¯ 7 * = Q ¯ 3 o ( 3 ) ( n ) . By simple calculation, we have m i ( Q ¯ i * ) 17 r n 9 , i = 6 , 8 , 9 , a contradiction to m i ( Q ) 9 r n 7 .

Case 2. Q x = F 2 ( n 1 ) . If d e g Q ( x ) 3 then Q N Q [ x ] is a forest with at most n 4 vertices, by Lemma 1.1, Theorems 2.2 and 2.4, we have that 9 r n 7 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) 3 r ( n 1 ) 4 + r ( n 4 ) 1 = 4 r n 5 . This is a contradiction. So we assume that deg Q ( x ) = 2 . There are 5 possibilities for graph Q. See Figure 17.

Note that Q ¯ 10 * = Q ¯ 2 ( n ) , Q ¯ 12 * = Q ¯ 2 ( n ) , Q ¯ 14 * = Q ¯ 3 o ( 4 ) ( n ) . By simple calculation, we have m i ( Q ¯ i * ) 3 r n 5 + 1 , i = 11 , 13 , a contradiction to m i ( Q ) 9 r n 7 .

Case 3. Q x F 3 ( n 1 ) . Since Q N Q [ x ] is a forest with at most n 3 vertices, by Lemma 1.1, Theorems 2.2 and 2.6, we have that

9 r n 7 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) 5 r ( n 1 ) 6 + r n 3 = 9 r n 7 . The equali-

Figure 16. The graphs Q ¯ i * , 1 i 9 .

ties holding imply that Q x F 3 ( n 1 ) and Q N Q [ x ] F 1 ( n 3 ) . There are 3 possibilities for graph Q. See Figure 18.

Note that Q ¯ 17 * = Q ¯ 3 o ( 1 ) ( n ) . By simple calculation, we have m i ( Q ¯ i * ) = 8 r n 7 , 15 i 16 , a contradiction to m i ( Q ) 9 r n 7 .

Theorem 3.4 If Q is a quasi-forest graph of even order n 8 having Q Q ¯ 1 ( n ) , Q ¯ 2 ( n ) , then m i ( Q ) 11 r n 8 . Furthermore, the equality holds if and

only if Q = Q 2 ( 8 ) n 8 2 P 2 .

Proof. It is straightforward to check that m i ( Q 2 ( 8 ) n 8 2 P 2 ) = 11 r n 8 . Let Q

be a quasi-forest graph of even order n 8 having Q Q ¯ 1 ( n ) , Q ¯ 2 ( n ) such that m i ( Q ) is as large as possible. Then m i ( Q ) 11 r n 8 . If Q is a forest, by Theorems 2.2, 2.4, 2.6, 2.8 and 2.10, we have that 11 r n 8 m i ( Q ) f 3 ( n ) = 5 r n 6 . This is a contradiction, so Q contains a coponent Q ^ with at least one cycle.

Let | Q ^ | = s . Suppose that Q Q ^ n s 2 P 2 . Since Q ^ is not a tree and Q Q ¯ 1 ( n ) , Q ¯ 2 ( n ) , by Lemma 1.2, Theorems 2.2, 2.4 and 2.7, we have that

m i ( Q ) = m i ( Q ^ ) m i ( Q Q ^ ) { 3 r s 4 3 r ( n s ) 4 , if s 4 is even , 3 7 r ( n 3 ) 7 , if s = 3 , ( r s 1 + 1 ) r ( n s ) 1 , if s 5 is odd , { 9 r n 8 , if s 4 is even , 21 r n 10 , if s = 3 , 5 r n 6 , if s 5 is odd , < 11 r n 8 ,

Figure 17. The graphs Q ¯ i * , 10 i 14 .

Figure 18. The graphs Q ¯ i * , 15 i 17 .

Figure 19. The graphs Q ¯ i * , 18 i 19 .

which is a contradiction. Hence we obtain that s is even and Q Q ^ = n s 2 P 2 .

Let x be the vertex in Q ^ such that Q ^ x is a forest and w ( Q ^ x ) be the number of components of Q ^ x . We consider the following two cases.

Case 1. w ( Q ^ x ) = 1 . Then Q ^ is a quasi-tree graph. Since

Q Q ¯ 1 ( n ) , Q ¯ 2 ( n ) it follows that s 8 . By Lemma 1.2 and Theorem 2.9, it follows that m i ( Q ) = ( 5 r s 6 + 1 ) r n s = 5 r n 6 + r n s 11 r n 8 . The equality holding

imply that s = 8 . In conclusion, Q = Q 2 ( 8 ) n 8 2 P 2 .

Case 2. w ( Q ^ x ) 2 . Then d e g x 3 . In addition, suppose that Q N Q [ x ] has a isolated vertex or d e g Q ( x ) 4 , by Lemma 1.1 and Theorem 2.2, we have that 11 r n 8 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) r ( n 1 ) 1 + r ( n 5 ) 1 = 5 r n 6 . This is a contradiction, hence, we have that d e g Q ( x ) = 3 and Q N Q [ x ] has no isolated vertex. For the case that Q x F 1 ( n 1 ) , by Lemma 1.1, Theorems 2.2 and 2.4, we have that 11 r n 8 m i ( Q ) m i ( Q x ) + m i ( Q N Q [ x ] ) 7 r ( n 1 ) 7 + r n 4 = 11 r n 8 . The equa- lities holding imply that Q x F 2 ( n 1 ) and Q N Q [ x ] F 1 ( n 4 ) . Since w ( Q ^ x ) 2 , there no such graph Q. For the other case that Q x F 1 ( n 1 ) , there are 2 possibilities for graph Q. See Figure 19.

Note that Q ¯ 18 * = Q ¯ 2 ( n ) and Q ¯ 19 * = Q 2 e ( 1 ) ( 8 ) n 8 2 P 2 when s = 8 . On the other hand, m i ( Q ¯ 19 * ) 21 r n 10 when s 10 , a contradiction to m i ( Q ) 11 r n 8 .

Cite this paper: Lin, J. and Jou, M. (2017) The Number of Maximal Independent Sets in Quasi-Tree Graphs and Quasi-Forest Graphs. Open Journal of Discrete Mathematics, 7, 134-147. doi: 10.4236/ojdm.2017.73013.
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.

 
 
Top