Communications in Analysis and Geometry
Volume 21 (2013)
Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator
Pages: 787 – 845
We study the spectrum of the normalized Laplace operator of a connected graph $Γ$. As is well known, the smallest non-trivial eigenvalue measures how difficult it is to decompose $Γ$ into two large pieces, whereas the largest eigenvalue controls how close $Γ$ is to being bipartite. The smallest eigenvalue can be controlled by the Cheeger constant, and we establish a dual construction that controls the largest eigenvalue. Moreover, we find that the neighborhood graphs $Γ[l]$ of order $l \geq 2$ encode important spectral information about $Γ$ itself which we systematically explore. In particular, the neighborhood graph method leads to new estimates for the smallest non-trivial eigenvalue that can improve the Cheeger inequality, as well as an explicit estimate for the largest eigenvalue from above and below. As applications of such spectral estimates, we provide a criterion for the synchronizability of coupled map lattices, and an estimate for the convergence rate of random walks on graphs.