Premium
Spectrum of the 1‐Laplacian and Cheeger's Constant on Graphs
Author(s) -
Chang K. C.
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21871
Subject(s) - mathematics , eigenvalues and eigenvectors , laplace operator , spectral graph theory , minimax , multiplicity (mathematics) , laplacian matrix , combinatorics , constant (computer programming) , spectrum (functional analysis) , algebraic connectivity , nonlinear system , discrete mathematics , graph , mathematical analysis , line graph , voltage graph , physics , quantum mechanics , computer science , programming language , mathematical optimization
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.