A tight upper bound of spectral radius in terms of degree deviation

Abstract

Let $G$ be a graph with $n$ vertices and $m$ edges. The spectral radius $\rho (G)$ of $G$ is the largest eigenvalue of the adjacency matrix of $G$. As is well known, $\rho (G)\ge \frac{2m}{n}$ with equality if and only if $G$ is regular. To bound $\rho (G)-\frac{2m}{n}$, Nikiforov (2006) introduced the degree deviation of $G$ as $$s(G)=\sum _{1\le i\le n}|d_i-\frac{2m}{n}|,$$ where $d_1,d_2,\dots ,d_n$ are the degrees of the vertices of $G$. Nikiforov conjectured that $\rho (G)-\frac{2m}{n}\le \sqrt{\frac{1}{2}s(G)}$ for sufficiently large $m$ and $n$. In this paper, we settle this conjecture without the assumption that $m$ and $n$ are large.