An improved lower bound on the independence number of a graph

The independence number of a graph GG, denoted α(G)α(G), is the maximum cardinality of an independent set of vertices in GG. Our main result is the strengthening of a lower bound for the independence number of a graph due to Löwenstein et al. (2011) who proved that if GG is a connected graph of order  nn and size  mm, then α(G)≥23n−14m−13. We show that if GG does not belong to a specific family of graphs, then α(G)>23n−14m. Further, we characterize the graphs GG for which α(G)≤23n−14m.