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

By Frank Bauer, Jürgen Jost. 2009

59 citations recorded by the source corpus.

We study the spectrum of the normalized Laplace operator of a connected graph $\Gamma$. As is well known, the smallest nontrivial eigenvalue measures how difficult it is to decompose $\Gamma$ into two large pieces, whereas the largest eigenvalue controls how close $\Gamma$ 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 $\Gamma[l]$ of order $l\geq2$ encode important spectral information about $\Gamma$ itself which we systematically explore. In particular, the neighborhood graph method leads to new estimates for the smallest nontrivial 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.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/acef8282e6bb05b336c85d9648cf59a0edb2938a

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

  1. Jürgen Jost
  2. Shiping Liu
  3. Frank Bauer
  4. Lorenzo Rosasco
  5. Raffaella Mulas

In Geometry and Topology

  1. Jürgen Jost
  2. Shiping Liu
  3. Frank Bauer
  4. Florentin Münch
  5. Raffaella Mulas
  6. Bin Zhu
  7. Ben Andrews
  8. Panyue Zhou

In Mathematical Physics

  1. Jürgen Jost
  2. Shiping Liu
  3. Frank Bauer
  4. Lorenzo Rosasco

Citations in the corpus