Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4603330 | Linear Algebra and its Applications | 2006 | 7 Pages |
Abstract
Let G be a graph whose Laplacian eigenvalues are 0 = λ1 ⩽ λ2 ⩽ ⋯ ⩽ λn. We investigate the gap (expressed either as a difference or as a ratio) between the extremal non-trivial Laplacian eigenvalues of a connected graph (that is λn and λ2). This gap is closely related to the average density of cuts in a graph. We focus here on the problem of bounding the gap from below.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory