2024/09/23 by Dieter Rautenbach, Rautenbach, Dieter, Florian Werner +1
Engineering · #Advanced Measurement and Metrology Techniques #Manufacturing Process and Optimization
paper · pdf · doi:10.48550/arxiv.2409.14956
For a finite, simple, and undirected graph G with n vertices, m edges, and largest eigenvalue λ, Nikiforov introduced the degree deviation of G as s=∑u∈ V(G)|dG(u)-(2m)/(n)|. Contributing to a conjecture of Nikiforov, we show λ-(2m)/(n)≤ √((2s)/(3)). For our result, we show that the largest eigenvalue of a graph that arises from a bipartite graph with mA,B edges by adding mA edges within one of the two partite sets is at most √mA+mA,B+√mA2+2mAmA,B, which is a common generalization of results due to Stanley and Bhattacharya, Friedland, and Peled.