Spectrum of the 1-Laplacian and Cheeger's Constant on Graphs

Abstract

We develop a nonlinear spectral graph theory, in which the Laplace operator is replaced by the 1 − Laplacian Δ1. The eigenvalue problem is to solve a nonlinear system involving a set valued function. In the study, we investigate the structure of the solutions, the minimax characterization of eigenvalues, the multiplicity theorem, etc. The eigenvalues as well as the eigenvectors are computed for several elementary graphs. The graphic feature of eigenvalues are also studied. In particular, Cheeger's constant, which has only some upper and lower bounds in linear spectral theory, equals to the first nonzero Δ1 eigenvalue for connected graphs.