Eigenvalues and degree deviation in graphs (Q819785)

The author shows that the difference \(\mu(G)-\frac{2m}{n}\) of the spectral radius of the adjacency matrix and the average degree in a graph is bounded both from below and from above by the function of the degree deviation \(s(G)=\sum_{u\in V(G)} | d(u)-\frac{2m}{n}| \), where \(d(u)\) is the degree of vertex \(u\). The author gives some further inequalities involving the eigenvalues and the degree deviation and shows that they are all tight to a constant factor. The paper also contains a useful section on efficient regularization, giving a good approximate answer to the question: ``What is the minimum number of edges that must be changed to obtain a regular graph?''