Article ID Journal Published Year Pages File Type
9655124 Discrete Applied Mathematics 2005 11 Pages PDF
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
, ,