DIMACS TR: 2005-18
Maximal and Maximum Independent Sets In Graphs With At Most $r$ Cycles
Authors: Bruce E. Sagan and Vincent R. Vatter
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.
Paper Available at:
DIMACS Home Page