A linear Cheeger inequality using eigenvector norms

DOI10.4310/JOC.2015.v6.n3.a2zbMath1323.05080arXiv1412.3195MaRDI QIDQ746827

Franklin H. J. Kenter

Publication date: 20 October 2015

Published in: Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.3195

zbMATH Keywords

Cheeger constant; graph partitioning; spectral graph theory; graph Laplacian

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity