A new lower bound on the independence number of graphs

摘要

We propose a new lower bound on the independence number of a graph. We show that our bound compares favorably to recent ones (e.g. Harant (2011) [12]). We obtain our bound by using the Bhatia-Davis inequality applied with analytical results (minimum, maximum, expectation and variance) of an algorithm for the vertex cover problem.