2005-17: Maximal Independent Sets In Graphs With At Most $r$ Cycles

DIMACS TR: 2005-17

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

Authors: Goh Chee Ying, Koh Khee Meng, Bruce E. Sagan and Vincent R. Vatter

ABSTRACT
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$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-17.ps.gz

DIMACS Home Page