Maximal and maximum independent sets in graphs with at most r cycles
With Bruce Sagan.
Journal of Graph Theory, 53 (2006), 283—314.
Let m(G) denote the number of maximal independent sets of vertices in a graph G and let c(n,r) be the maximum value of m(G) over all connected graphs with n vertices and at most r cycles. A theorem of Griggs, Grinstead, and Guichard gives a formula for c(n,r) when r is large relative to n, while a theorem of Goh, Koh, Sagan, and Vatter does the same when r is small relative to n. We complete the determination of c(n,r) for all n and r and characterize the extremal graphs. Problems for maximum independent sets are also completely resolved.
Download the paper:
- download from the journal website (subscription required)
- ps
- source
Related links:
- This paper is a follow-up to “Maximal independent sets in graphs with at most r cycles.”
- Slides for a talk at the Rutgers Graduate Student Combinatorics Seminar, available in pdf, ps, or source