The lower bound on independence number

Let G be a graph with degree sequence (d v). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least ∑ vf m+1(d v), where f m+1(x) is a function greater than log(x/(m+1)) - 1/x for x > 0. For a weighted graph G = (V, E, w), we prove that its weighted independence number (the maximum sum of the weights of an independent set in G) is at least ∑ v w v/1 + d v where w v is the weight of v.link_to_subscribed_fulltex