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

2005/05/03 by Bruce E. Sagan, Sagan, Bruce E., V. Vatter +1 · 1 citation
Mathematics · #05C35 (Primary) 05C69 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05C69

paper · pdf · doi:10.48550/arxiv.math/0505048

30 pages, 9 figures, Latex, see related papers at http://www.math.msu.edu/~sagan

arxiv created 2005/05/03 · arxiv updated 2009/12/01

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.

Cited by

• A note on the second-largest number of dissociation sets in connected graphs

Related

• Maximal Independent Sets In Graphs With At Most r Cycles
• Maximizing the number of maximal independent sets of a fixed size
• Maximal independent sets in graphs with given matching number
• The number of maximal independent sets in connected graphs
• On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza