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

作　　者：Jenq-Jong Lin Min-Jen Jou 

机构地区：[1]Ling Tung University, Taichung, Taiwan

出　　处：《Open Journal of Discrete Mathematics》2017年第3期134-147,共14页离散数学期刊（英文）

摘　　要：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.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.

关 键 词：MAXIMAL Independent Set Quasi-Tree GRAPH Quasi-Forest GRAPH EXTREMAL GRAPH 

分 类 号：O1[理学—数学]