Random walks and local cuts in graphs |
| |
Authors: | Fan Chung |
| |
Institution: | University of California, San Diego, Department of Mathematics, La Jolla, CA 92093, United States |
| |
Abstract: | For a specified subset S of vertices in a graph G we consider local cuts that separate a subset of S. We consider the local Cheeger constant which is the minimum Cheeger ratio over all subsets of S, and we examine the relationship between the local Cheeger constant and the Dirichlet eigenvalue of the induced subgraph on S. These relationships are summarized in a local Cheeger inequality. The proofs are based on the methods of establishing isoperimetric inequalities using random walks and the spectral methods for eigenvalues with Dirichlet boundary conditions. |
| |
Keywords: | 05C50 15A18 60J10 68R10 |
本文献已被 ScienceDirect 等数据库收录! |
|