Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian

Frank Bauer and Jürgen Jost

Contact the author: Please use for correspondence this email.
Submission date: 02. Jun. 2010
published in: Communications in analysis and geometry, 21 (2013) 4, p. 787-845 
DOI number (of the published article): 10.4310/CAG.2013.v21.n4.a2
Bibtex
with the following different title: Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator
MSC-Numbers: 05C50
Keywords and phrases: graph laplacian, largest eigenvalue, Cheeger constant, neighborhood graph

Abstract:
We study the spectrum of the normalized Laplace operator of a connected graph . As is well known, the smallest nontrivial 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 of order encode important spectral information about itself which we systematically explore. In particular, we can derive new estimates for the smallest nontrivial eigenvalue that improve the Cheeger estimate for certain graphs, 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.