New spectral lower bounds on the bisection width of graphs

DOI10.1016/j.tcs.2004.03.059zbMath1067.05046OpenAlexW1981941088MaRDI QIDQ596083

Burkhard Monien, Robert Elsässer, Sergei L. Bezrukov, Robert Preis, Jean-Pierre Tillich

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.03.059

zbMATH Keywords

Eigenvalues of graphsGraph bisectionLaplacian of graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Minors in graphs of large \(\theta_r\)-girth ⋮ Low Polynomial Exclusion of Planar Graph Patterns ⋮ Pathwidth vs Cocircumference ⋮ Packing and Covering Induced Subdivisions ⋮ Pathwidth of cubic graphs and exact algorithms

Cites Work

• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ramanujan graphs
• Eigenvalues and expanders
• The isoperimetric number of random regular graphs
• On the second eigenvalue of a graph
• Cubic Ramanujan graphs
• Some simplified NP-complete graph problems
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• On spectral bounds for the \(k\)-partitioning of graphs
• Isoperimetric numbers of graphs
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item