Sharp spectral bounds of several graph parameters using eigenvector norms

DOI10.1016/J.LAA.2016.03.026zbMATH Open1338.05163OpenAlexW2329875035MaRDI QIDQ286136FDOQ286136

Authors: Franklin Kenter 

Publication date: 20 May 2016

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

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

Recommendations

• Tighter spectral bounds for the cut size, based on Laplacian eigenvectors
• scientific article; zbMATH DE number 1189239
• A class of spectral bounds for max \(k\)-cut
• Many sparse cuts via higher eigenvalues
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs

zbMATH Keywords

spectral graph theorydensest subgraph3-way maximum cutexpander mixing lemmamaximum cut

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42)

Cites Work

• Title not available (Why is that?)
• Hermitian matrices and graphs: Singular values and discrepancy
• Some optimal inapproximability results
• The dense \(k\)-subgraph problem
• Using discrepancy to control singular values for nonnegative matrices
• Lifts, discrepancy and nearly optimal spectral gap
• Title not available (Why is that?)
• Explicit construction of linear sized tolerant networks
• The dual Cheeger constant and spectra of infinite graphs
• Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• From quasirandom graphs to graph limits and graphlets
• Discrepancy inequalities for directed graphs
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Max cut and the smallest eigenvalue

Cited In (2)

• A unified framework for the expander mixing lemma for irregular graphs and its applications
• On the sharpness of spectral estimates for graph Laplacians

This page was built for publication: Sharp spectral bounds of several graph parameters using eigenvector norms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286136)