New results on eigenvalues and degree deviation

MaRDI QIDQ6249709zbMATH OpenFDO

Authors Felix Goldberg

Publication date 11 March 2014

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42) Social networks; opinion dynamics (91D30) Vertex degrees (05C07)

Abstract: Let $G$ be a graph. In a famous paper Collatz and Sinogowitz had proposed to measure its deviation from regularity by the difference of the (adjacency) spectral radius and the average degree: $epsilon(G)=ho(G)-frac2mn$. We obtain here a new upper bound on $epsilon(G)$ which seems to consistently outperform the best known upper bound to date, due to Nikiforov. The method of proof may also be of independent interest, as we use notions from numerical analysis to re-cast the estimation of $epsilon(G)$ as a special case of the estimation of the difference between Rayleigh quotients of proximal vectors.

This page was built for publication: New results on eigenvalues and degree deviation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6249709)