An Optimization Approach to Degree Deviation and Spectral Radius

2024/12/19 by Dieter Rautenbach, Rautenbach, Dieter, Florian Werner +1
Engineering · #Advanced Measurement and Metrology Techniques

paper · pdf · doi:10.48550/arxiv.2412.14936

Abstract

For a finite, simple, and undirected graph G with n vertices and average degree d, Nikiforov introduced the degree deviation of G as s=∑_{u∈ V(G)}|d_G(u)-d|. Provided that G has largest eigenvalue λ, minimum degree at least δ, and maximum degree at most Δ, where 0≤δ (dn)/(√(2)). \endcases Our results are based on a smoothing technique relating the degree deviation and the largest eigenvalue to low-dimensional non-linear optimization problems.

Related

• Degree Deviation and Spectral Radius
• A tight upper bound of spectral radius in terms of degree deviation
• New results on eigenvalues and degree deviation
• Eigenvalues and degree deviation in graphs
• Spectral radius minus average degree: a better bound