New results on eigenvalues and degree deviation

arXiv1403.2629MaRDI QIDQ6249709FDOQ6249709

Authors: Felix Goldberg 

Publication date: 11 March 2014

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.

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)

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)