Geodesic
An upper bound for the number of maximal independent sets in a~graph
Diskretnaya Matematika, Tome 19 (2007) no. 3, pp. 84-88.

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

Let $T(G)$ be the number of maximal independent sets, $M(G)$ be the number of generated matchings in a graph $G$. We prove the inequality $T(G)\le M(G)+1$. As a corollary, we derive the bound $T(G)\le((m-m_1)/p+1)^p+m_1$ for a graph containing no generated subgraph $(p+1)K_2$, where $m$ is the number of edges and $m_1$ is the number of dominating edges. This inequality differs from the Balas–Yu conjecture only in the presence of the last term. 
@article{DM_2007_19_3_a6,
     author = {V. E. Alekseev},
     title = {An upper bound for the number of maximal independent sets in a~graph},
     journal = {Diskretnaya Matematika},
     pages = {84--88},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_3_a6/}
}
TY  - JOUR
AU  - V. E. Alekseev
TI  - An upper bound for the number of maximal independent sets in a~graph
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 84
EP  - 88
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_3_a6/
LA  - ru
ID  - DM_2007_19_3_a6
ER  - 
%0 Journal Article
%A V. E. Alekseev
%T An upper bound for the number of maximal independent sets in a~graph
%J Diskretnaya Matematika
%D 2007
%P 84-88
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_3_a6/
%G ru
%F DM_2007_19_3_a6
V. E. Alekseev. An upper bound for the number of maximal independent sets in a~graph. Diskretnaya Matematika, Tome 19 (2007) no. 3, pp. 84-88. http://geodesic.mathdoc.fr/item/DM_2007_19_3_a6/

[1] Alekseev V. E., “O chisle tupikovykh nezavisimykh mnozhestv v grafakh iz nasledstvennykh klassov”, Kombinatorno-algebraicheskie metody v diskretnoi optimizatsii, Gorkii, 1991, 5–8

[2] Balas E., Yu Ch. S., “On graphs with polynomially solvable maximum-weight clique problem”, Networks, 19 (1989), 247–253 | DOI | MR | Zbl

[3] Farber M., Hujter M., Tuza Z., “An upper bound on the number of cliques in a graph”, Networks, 23 (1993), 207–210 | DOI | MR | Zbl

[4] Moon J. W., Moser L., “On cliques in graphs”, Israel J. Math., 3 (1965), 23–28 | DOI | MR | Zbl

[5] Tsukigama S., Ide M., Ariochi H., Ozaki H., “A new algorithm for generating all the maximal independent sets”, SIAM J. Comput., 6:3 (1977), 505–517 | DOI | MR