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 &isin;V(G) such that G &minus; 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.
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