2005-18: Maximal and Maximum Independent Sets In Graphs With At Most $r$ Cycles

DIMACS TR: 2005-18

Maximal and Maximum Independent Sets In Graphs With At Most $r$ Cycles

Authors: Bruce E. Sagan and Vincent R. Vatter

ABSTRACT
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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-18.ps.gz

DIMACS Home Page