Maximal and maximum independent sets in graphs with at most r cycles

Bruce E. Sagan, Vincent R. Vatter

Research output: Contribution to journalArticlepeer-review

29 Citations (Scopus)


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. (C) 2006 Wiley Periodicals, Inc.

Original languageEnglish
Pages (from-to)283-314
Number of pages32
JournalJournal of Graph Theory
Publication statusPublished - Dec 2006


  • cycle
  • ear decomposition
  • maximal and maximum independent set


Dive into the research topics of 'Maximal and maximum independent sets in graphs with at most r cycles'. Together they form a unique fingerprint.

Cite this