Author(s)

Min-Jen Jou¹, Jenq-Jong Lin²

¹Department of Information Technology, Ling Tung University, Taichung City.
²Department of Finance, Ling Tung University, Taichung City.

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.

Maximal Independent Set, Connected Graph Having at Most Two Cycles

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.