%0 Journal Article
%T The Number of Maximal Independent Sets in Quasi-Tree Graphs and Quasi-Forest Graphs
%A Jenq-Jong Lin
%A Min-Jen Jou
%J Open Journal of Discrete Mathematics
%P 134-147
%@ 2161-7643
%D 2017
%I Scientific Research Publishing
%R 10.4236/ojdm.2017.73013
%X A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) <em>G</em> with vertex set <span style=\"white-space:nowrap;\"><em>V(G)</em></span> is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex <span style=\"white-space:nowrap;\"><em>x</em> &amp;isin;<em>V(G)</em></span> such that <span style=\"white-space:nowrap;\"><em>G</em> &amp;minus; <em>x</em>&nbsp;</span>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.
%K Maximal Independent Set
%K Quasi-Tree Graph
%K Quasi-Forest Graph
%K Extremal  Graph
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=77461