Maximal independent sets in graphs with at most r cycles
With Goh Chee Ying, Koh Khee Meng, and Bruce Sagan.
Journal of Graph Theory, 53 (2006), 270—282.
We find the maximum number of maximal independent sets in two families of graphs. The first family consists of all graphs with n vertices and at most r cycles. The second family is all graphs of the first family which are connected and satisfy n ≥ 3r.
Download the paper:
- download from the journal website (subscription required)
- ps
- source
Related links:
- This work is followed up in “Maximal and maximum independent sets in graphs with at most r cycles.”