Back
 OJDM  Vol.6 No.4 , October 2016
An Alternative Proof of the Largest Number of Maximal Independent Sets in Connected Graphs Having at Most Two Cycles
Abstract: G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.
Cite this paper: Jou, M. and Lin, J. (2016) An Alternative Proof of the Largest Number of Maximal Independent Sets in Connected Graphs Having at Most Two Cycles. Open Journal of Discrete Mathematics, 6, 227-237. doi: 10.4236/ojdm.2016.64019.
References

[1]   Ying, G.C., Meng, Y.Y., Sagan, B.E. and Vatter, V.R. (2006) Maximal Independent Sets in Graphs with at Most r Cycles. Journal of Graph Theory, 53, 270-282.
http://dx.doi.org/10.1002/jgt.20185

[2]   Moon, J.W. and Moser, L. (1965) On Cliques in Graphs. Israel Journal of Mathematics, 3, 23-28.
http://dx.doi.org/10.1007/BF02760024

[3]   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 Mathematical Conference, World Scientific, Singapore City, 265-275.

[4]   Jin, Z. and Li, X. (2008) Graphs with the Second Largest Number of Maximal Independent Sets. Discrete Mathematics, 308, 5864-5870.
http://dx.doi.org/10.1016/j.disc.2007.10.032

[5]   Prodinger, H. and Tichy, R.F. (1982) Fibonacci Numbers of Graphs. The Fibonacci Quarterly, 20, 16-21.

[6]   Knopfmacher, A., Tichy, R.F., Wagner, S. and Ziegler, V. (2007) Graphs, Partitions and Fibonacci Numbers. Discrete Applied Mathematics, 155, 1175-1187.
http://dx.doi.org/10.1016/j.dam.2006.10.010

[7]   Wagner, S.G. (2006) The Fibonacci Number of Generalized Petersen Graphs. The Fibonacci Quarterly, 44, 362-367.

[8]   Jou, M.J. and Chang, G.J. (2002) Algorithmic Aspects of Counting Independent Sets. Ars Combinatoria, 65, 265-277.

[9]   Jou, M.J. and Chang, G.J. (1997) Maximal Independent Sets in Graphs with at Most One Cycle. Discrete Applied Mathematics, 79, 67-73.
http://dx.doi.org/10.1016/S0166-218X(97)00033-4

[10]   Sagan, B.E. and Vatter, V.R. (2006) Maximal and Maximum Independent Sets in Graphs with at Most r Cycles. Journal of Graph Theory, 53, 283-314.
http://dx.doi.org/10.1002/jgt.20186

[11]   Jou, M.J. (2012) The Second Largest Number of Maximal Independent Sets in Connected Graphs with at Most One Cycle. Journal of Combinatorial Optimization, 24, 192-201.
http://dx.doi.org/10.1007/s10878-011-9376-4

[12]   Hujter, M. and Tuza, Z. (1993) The Number of Maximal Independent Sets in Triangle-Free Graphs. SIAM: SIAM Journal on Discrete Mathematics, 6, 284-288.
http://dx.doi.org/10.1137/0406022

[13]   Jou, M.J. (1991) The Number of Maximal Independent Sets in Graphs. Master Thesis, Department of Mathematics, National Central University, Taoyuan.

 
 
Top