Preprint 30/2010

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
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

We study the spectrum of the normalized Laplace operator of a connected graph formula3. As is well known, the smallest nontrivial eigenvalue measures how difficult it is to decompose formula3 into two large pieces, whereas the largest eigenvalue controls how close formula3 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 formula9 of order formula11 encode important spectral information about formula3 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.

18.10.2019, 02:14