Authors:
J. Harant, S. Mohr
Title:
On Selkow's bound on the independence number of graphs
Source:
Discussiones Mathematicae Graph Theory
Received 20.11.2017, Revised 20.11.2017, Accepted 18.12.2017, doi: 10.7151/dmgt.2100

Abstract:
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)\frac{1}{d(v)+1}\bigg(1+\max\bigg{\frac{d(v)}{d(v)+1}-∑u∈N(v)\frac{1}{d(u)+1},0 \bigg}\bigg) 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

Links:
PDF