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: |