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, quas...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.
基金supported by the Joint Fund of the State Key Laboratory of Coal Resources and Safe Mining-Beijing University Outstanding Young Scientists Program Project (BJJWZYJH01201911413037)State Key Laboratory of“Coal Resources and Safe Mining”Open Fund (SKLCRSM19ZZ02)。