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

Simple item page
dc.creatorSagan, Bruce E.
dc.creatorVatter, V.
dc.date2005-05-03
dc.date.accessioned2026-07-07T05:19:36Z
dc.date.available2026-07-07T05:19:36Z
dc.descriptionLet 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.
dc.description30 pages, 9 figures, Latex, see related papers at http://www.math.msu.edu/~sagan
dc.identifierhttps://arxiv.org/abs/math/0505048
dc.identifierhttp://arxiv.org/abs/math/0505048
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/75076
dc.subjectCombinatorics
dc.subject05C35 (Primary) 05C69 (Secondary)
dc.titleMaximal and Maximum Independent Sets In Graphs With At Most r Cycles
dc.typetext

Files

Collections

arXiv