Tighter spectral bounds for the cut size, based on Laplacian eigenvectors

DOI10.1016/j.laa.2019.02.025zbMath1411.05159OpenAlexW2921515315MaRDI QIDQ2419023

Karel Devriendt, Piet Van Mieghem

Publication date: 29 May 2019

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2019.02.025

zbMATH Keywords

Laplacian matrixspectral graph theoryCheeger inequalitygraph cutnetwork epidemics

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Old and new results on algebraic connectivity of graphs
• Explicit construction of linear sized tolerant networks
• Eigenvalues and expanders
• The complexity of testing whether a graph is a superconcentrator
• Laplacian eigenvalues and the maximum cut problem
• Isoperimetric numbers of graphs
• Graph Implementations for Nonsmooth Convex Programs
• Expander graphs and their applications
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Reducibility among Combinatorial Problems
• Performance Analysis of Complex Networks and Systems
• The Isoperimetric Problem
• Optimal numberings and isoperimetric problems on graphs
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: Tighter spectral bounds for the cut size, based on Laplacian eigenvectors