Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9655124 | Discrete Applied Mathematics | 2005 | 11 Pages |
Abstract
In this paper, we determine upper and lower bounds for the number of independent sets in a unicyclic graph in terms of its order. This gives an upper bound for the number of independent sets in a connected graph which contains at least one cycle. We also determine the upper bound for the number of independent sets in a unicyclic graph in terms of order and girth. In each case, we characterize the extremal graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Anders Sune Pedersen, Preben Dahl Vestergaard,