For a finite, simple, and undirected graph $G$ with $n$ vertices, $m$ edges, and largest eigenvalue $\lambda$, 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 $\lambda-\frac{2m}{n}\leq \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_Am_{A,B}}},$$which is a common generalization of results due to Stanley and Bhattacharya, Friedland, and Peled.
@article{10_37236_13471,
author = {Dieter Rautenbach and Florian Werner},
title = {Degree deviation and spectral radius},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {2},
doi = {10.37236/13471},
zbl = {1569.05218},
url = {http://geodesic.mathdoc.fr/articles/10.37236/13471/}
}
TY - JOUR
AU - Dieter Rautenbach
AU - Florian Werner
TI - Degree deviation and spectral radius
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/13471/
DO - 10.37236/13471
ID - 10_37236_13471
ER -
%0 Journal Article
%A Dieter Rautenbach
%A Florian Werner
%T Degree deviation and spectral radius
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/13471/
%R 10.37236/13471
%F 10_37236_13471
Dieter Rautenbach; Florian Werner. Degree deviation and spectral radius. The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/13471
