Geodesic
On Selkow’s Bound on the Independence Number of Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 655-657

Voir la notice de l'article provenant de la source Library of Science

For a graph G with vertex set V (G) and independence number α (G), Selkow [A Probabilistic lower bound on the independence number of graphs, Discrete Math. 132 (1994) 363–365] established the famous lower bound ∑_ v ∈ V (G) 1d(v)+1 ( 1+ max{ d(v) d(v)+1 - ∑_ u ∈ N(v) 1 d(u)+1 ,0 } ) on α (G), where N(v) and d(v) = | N(v) | denote the neighborhood and the degree of a vertex v ∈ V (G), respectively. However, Selkow’s original proof of this result is incorrect. We give a new probabilistic proof of Selkow’s bound here.
Keywords: graph, independence number 
@article{DMGT_2019_39_3_a3,
     author = {Harant, Jochen and Mohr, Samuel},
     title = {On {Selkow{\textquoteright}s} {Bound} on the {Independence} {Number} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {655--657},
     publisher = {mathdoc},
     volume = {39},
     number = {3},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a3/}
}
TY  - JOUR
AU  - Harant, Jochen
AU  - Mohr, Samuel
TI  - On Selkow’s Bound on the Independence Number of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 655
EP  - 657
VL  - 39
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a3/
LA  - en
ID  - DMGT_2019_39_3_a3
ER  - 
%0 Journal Article
%A Harant, Jochen
%A Mohr, Samuel
%T On Selkow’s Bound on the Independence Number of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 655-657
%V 39
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a3/
%G en
%F DMGT_2019_39_3_a3
Harant, Jochen; Mohr, Samuel. On Selkow’s Bound on the Independence Number of Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 655-657. http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a3/