Spectral radius minus average degree: a better bound

2014/07/16 by Felix Goldberg, Goldberg, Felix
Computer Science · Mathematics · #05C07 #05C50 #15A42 #26D15 #26D20 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C07 #msc:05C50 #msc:15A42 #msc:26D15 #msc:26D20

paper · pdf · doi:10.48550/arxiv.1407.4285

arxiv created 2014/07/16 · openalex publication_date 2014/07/16 · arxiv updated 2014/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Collatz and Sinogowitz had proposed to measure the departure of a graph G from regularity by the difference of the (adjacency) spectral radius and the average degree: ε(G)=ρ(G)-(2m)/(n). We give here new lower bounds on this quantity, which improve upon the currently known ones.

Related

• New results on eigenvalues and degree deviation
• A (forgotten) upper bound for the spectral radius of a graph
• A tight upper bound of spectral radius in terms of degree deviation
• A New Lower Bound on the Spectral Radius of Graphs with Prescribed Average Degree
• An Optimization Approach to Degree Deviation and Spectral Radius