Abstract
The generalized conductance ϕ(G,H) between two weighted graphs G and H on the same vertex set V is defined as the ratio [Formula presented] where capG(S,S¯) is the total weight of the edges crossing from vertex set S⊆V to S¯=V−S. We show that the minimum generalized eigenvalue λ(LG,LH) of the pair of Laplacians LG and LH satisfies ϕ(G,H)≥λ(LG,LH)≥ϕ(G,H)ϕ(G)/16, where ϕ(G) is the standard conductance of G. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to λ(LG,LH).
Original language | English (US) |
---|---|
Pages (from-to) | 139-152 |
Number of pages | 14 |
Journal | Linear Algebra and Its Applications |
Volume | 665 |
DOIs | |
State | Published - May 15 2023 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Algebra and Number Theory
- Numerical Analysis
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Keywords
- Cheeger inequality
- Generalized cuts
- Spectral graph theory