|
This article is cited in 31 scientific papers (total in 31 papers)
On the number of independent sets in extenders
A. A. Sapozhenko
Abstract:
We improve Alon's upper bound for the number of independent sets in regular graphs and extend it to almost regular graphs. We also present an upper bound for the number of independent sets of non-typical size for almost regular graphs and an upper bound of the form $2^{(n/2)(1-c\delta)}$, where $c$ is a constant, for the number of independent sets in almost regular $\delta$-expanders.
Received: 15.12.2000
Citation:
A. A. Sapozhenko, “On the number of independent sets in extenders”, Diskr. Mat., 13:1 (2001), 56–62; Discrete Math. Appl., 11:2 (2001), 155–161
Linking options:
https://www.mathnet.ru/eng/dm276https://doi.org/10.4213/dm276 https://www.mathnet.ru/eng/dm/v13/i1/p56
|
Statistics & downloads: |
Abstract page: | 958 | Full-text PDF : | 408 | References: | 101 | First page: | 3 |
|