Eigenvalues and degree deviation in graphs

By Vladimir Nikiforov. 2005

63 citations recorded by the source corpus.

Abstract Let G be a graph with n vertices and m edges and let μ(G) = μ1(G) ⩾ ⋯ ⩾ μn(G) be the eigenvalues of its adjacency matrix. Set s ( G ) = ∑ u ∈ V ( G ) ∣ d ( u ) - 2 m / n ∣ . We prove that s 2 ( G ) 2 n 2 2 m ⩽ μ ( G ) - 2 m n ⩽ s ( G ) . In addition we derive similar inequalities for bipartite G. We also prove that the inequality μ k ( G ) + μ n - k + 2 ( G ¯ ) ⩾ - 1 - 2 2 s ( G ) holds for every k = 2, … , n. Finally we prove that for every graph G of order n, μ n ( G ) + μ n ( G ¯ ) ⩽ - 1 - s 2 ( G ) 2 n 3 . We show that these inequalities are tight up to a constant factor.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/15748fc5a9bf0205f319196743579a41212873c2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Bounds on graph eigenvalues I (2006, background): “unlessG = T r(n). 1 Next, let G be a graph of order n, size m, and maximum degree ∆(G) = ∆. One of the best known facts about µ(G) is the inequality µ(G) ≥ 2m/n, due to Collatz and Sinogovitz [4]. In [11] we gave upper and lower bounds on µ(G)−2m/n in terms of degree deviation. In turn, Cioab˘a and ”
Bounds on graph eigenvalues II (2006, background): “In [11] we gave upper and lower bounds on μ(G) − 2m/n in terms of degree deviation.”