An Alternative Proof of the Largest Number of Maximal Independent Sets in Connected Graphs Having at Most Two Cycles

Min-Jen  Jou; Jenq-Jong  Lin

doi:10.4236/ojdm.2016.64019

Search Menu Sign in

Journals by Subject

Journals by Title

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

Min-Jen Jou¹, Jenq-Jong Lin²

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.

Keywords: Maximal Independent Set, Connected Graph Having at Most Two Cycles

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.