An Optimization Approach to Degree Deviation and Spectral Radius

For a finite, simple, and undirected graph $G$ with $n$ vertices and average degree $d$, Nikiforov introduced the degree deviation of $G$ as $s={\sum }_{u\in V(G)}\mid d_G(u)-d\mid$. Provided that $G$ has largest eigenvalue $\lambda$, minimum degree at least $\delta$, and maximum degree at most $\mathrm{\Delta }$, where $0\le \delta <d<\mathrm{\Delta }<n$, we show $$s\le \frac{2n(\mathrm{\Delta }-d)(d-\delta )}{\mathrm{\Delta }-\delta }and\lambda \ge \{\begin{array}{ll}\frac{d^{2}n}{\sqrt{d^2{n}^2-s^2}}& ,ifs\le \frac{dn}{\sqrt{2}},\\ \frac{2s}{n}& ,ifs>\frac{dn}{\sqrt{2}}\mathrm{.}\end{array}$$ Our results are based on a smoothing technique relating the degree deviation and the largest eigenvalue to low-dimensional non-linear optimization problems.