Minimum cuts, girth and a spectral threshold

DOI10.1016/j.ipl.2003.10.009zbMath1183.68413OpenAlexW2060254469MaRDI QIDQ1029057

L. Sunil Chandran

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.10.009

zbMATH Keywords

girthLaplacian spectrumgraph algorithmsminimum cuts

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

Spectral Bounds for the Connectivity of Regular Graphs with Given Order ⋮ The second largest eigenvalue and vertex-connectivity of regular multigraphs ⋮ Sharp spectral bounds for the vertex-connectivity of regular graphs ⋮ Edge-connectivity and (signless) Laplacian eigenvalue of graphs ⋮ Sharp spectral bounds for the edge-connectivity of regular graphs ⋮ Connectivity and eigenvalues of graphs with given girth or clique number ⋮ Spectral radius and \(k\)-connectedness of a graph ⋮ Vertex-connectivity and eigenvalues of graphs with fixed girth ⋮ Vertex-connectivity and eigenvalues of graphs ⋮ Edge-connectivity in regular multigraphs from eigenvalues ⋮ Eigenvalues and edge-connectivity of regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Ramanujan graphs
• Eigenvalues, diameter, and mean distance in graphs
• Parallel concepts in graph theory
• The Moore bound for irregular graphs
• A new series of dense graphs of high girth
• A High Girth Graph Construction

This page was built for publication: Minimum cuts, girth and a spectral threshold