Contents Online

# Communications in Analysis and Geometry

## Volume 21 (2013)

### Number 4

### Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator

Pages: 787 – 845

DOI: http://dx.doi.org/10.4310/CAG.2013.v21.n4.a2

#### Authors

#### Abstract

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.

Published 5 July 2013