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/