Geodesic
On the number of independent sets in graphs with fixed independence number
Diskretnaya Matematika, Tome 19 (2007) no. 2, pp. 63-66 
A. B. Dainiak. On the number of independent sets in graphs with fixed independence number. Diskretnaya Matematika, Tome 19 (2007) no. 2, pp. 63-66. http://geodesic.mathdoc.fr/item/DM_2007_19_2_a5/
@article{DM_2007_19_2_a5,
     author = {A. B. Dainiak},
     title = {On the number of independent sets in graphs with fixed independence number},
     journal = {Diskretnaya Matematika},
     pages = {63--66},
     year = {2007},
     volume = {19},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_2_a5/}
}
TY  - JOUR
AU  - A. B. Dainiak
TI  - On the number of independent sets in graphs with fixed independence number
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 63
EP  - 66
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_2_a5/
LA  - ru
ID  - DM_2007_19_2_a5
ER  - 
%0 Journal Article
%A A. B. Dainiak
%T On the number of independent sets in graphs with fixed independence number
%J Diskretnaya Matematika
%D 2007
%P 63-66
%V 19
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2007_19_2_a5/
%G ru
%F DM_2007_19_2_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

We construct a sequence of graphs of large degree with growing number of vertices for which the number of independent sets is substantially greater than the number of all subsets of the independent set of maximal cardinality.

[1] Sapozhenko A. A., “Dokazatelstvo gipotezy Kamerona–Erdesha o chisle mnozhestv, svobodnykh ot summ”, Matem. voprosy kibern., 12 (2003), 5–14

[2] Sapozhenko A. A., “O chisle nezavisimykh mnozhestv v rasshiritelyakh”, Diskretnaya matematika, 13:1 (2001), 56–62 | MR | Zbl

[3] Kharari F., Teoriya grafov, Mir, Moskva, 1973 | MR

[4] Alon N., “Independent sets in regular graphs and sum-free subsets of finite groups”, Israel J. Math., 73:2 (1991), 247–256 | DOI | MR | Zbl