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

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

2005-05-03

arxiv.org/abs/math/0505048v1

Mathematics

Combinatorics

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Maximal and Maximum Independent Sets In Graphs With At Most r Cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximal and Maximum Independent Sets In Graphs With At Most r Cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximal and Maximum Independent Sets In Graphs With At Most r Cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-460514