Degree Deviation and Spectral Radius

Abstract

For a finite, simple, and undirected graph $G$ with $n$ vertices, $m$ edges, and largest eigenvalue $\hat{I}»$, Nikiforov introduced the degree deviation of $G$ as $s={\sum }_{u\in V(G)}\left|d_G(u)-\frac{2m}{n}\right|$. Contributing to a conjecture of Nikiforov, we show $\hat{I}»-\frac{2m}{n}\le \sqrt{\frac{2s}{3}}$. For our result, we show that the largest eigenvalue of a graph that arises from a bipartite graph with $m_{A,B}$ edges by adding $m_A$ edges within one of the two partite sets is at most $\sqrt{m_A+m_{A,B}+\sqrt{m_A^2+2m_A{m}_{A,B}}}$, which is a common generalization of results due to Stanley and Bhattacharya, Friedland, and Peled.