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 ) 1 d ( 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.
展开▼
