A tight upper bound of spectral radius in terms of degree deviation

2024/11/02 by Zhang, Wenqian
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2411.01207

Abstract

Let G be a graph with n vertices and m edges. The spectral radius ρ(G) of G is the largest eigenvalue of the adjacency matrix of G. As is well known, ρ(G)≥(2m)/(n) with equality if and only if G is regular. To bound ρ(G)-(2m)/(n), Nikiforov (2006) introduced the degree deviation of G as s(G)=∑_{1≤ i≤ n}|d_i-(2m)/(n)|, where d₁,d₂,…,d_n are the degrees of the vertices of G. Nikiforov conjectured that ρ(G)-(2m)/(n)≤√((1)/(2)s(G)) for sufficiently large m and n. In this paper, we settle this conjecture without the assumption that m and n are large.

Related

• Degree Deviation and Spectral Radius
• An Optimization Approach to Degree Deviation and Spectral Radius
• On the α-spectral radius of graphs
• New results on eigenvalues and degree deviation
• The spectral radius and the maximum degree of irregular graphs