Lower bounds on the independence number of a graph in terms of degrees

Given an integer $\mathrm{\Delta }\ge 3$, let ${\mathcal{G}}_{\mathrm{\Delta }}$ be the set of connected graphs $G\mathrm{\ne }{K}_{\mathrm{\Delta }+1}$ with maximum degree $\mathrm{\Delta }$ and, for $i=1,\cdots ,\mathrm{\Delta }$, let $V_i(G)$ be the set of vertices of $G$ of degree $i$. \ We prove that ${\sum }_{i=1}^{\mathrm{\Delta }}{c}_i\mathrm{\mid }{V}_i(G)\mathrm{\mid }$ is a lower bound on the independence number $\alpha (G)$ of $G\in {\mathcal{G}}_{\mathrm{\Delta }}$, where $c_{\mathrm{\Delta }}=\frac{1}{\mathrm{\Delta }}$ and $i{c}_i=1-c_{i+1}$ for $i=1,\cdots ,\mathrm{\Delta }-1$. Moreover, if $\epsilon >0$ and $j\in \{1,\cdots ,\mathrm{\Delta }\}$, then the inequality $\alpha (G)\ge \epsilon \mathrm{\mid }{V}_j(G)\mathrm{\mid }+{\sum }_{i=1}^{\mathrm{\Delta }}{c}_i\mathrm{\mid }{V}_i(G)\mathrm{\mid }$ does not hold for infinitely many graphs $G\in {\mathcal{G}}_{\mathrm{\Delta }}$. We also show that an independent set $I\subset V(G)$ of $G\in {\mathcal{G}}_{\mathrm{\Delta }}$ such that $\mathrm{\mid }I\mathrm{\mid }\ge {\sum }_{i=1}^{\mathrm{\Delta }}{c}_i\mathrm{\mid }{V}_i(G)\mathrm{\mid }$ can be found in polynomial time.