A spectral lower bound for the treewidth of a graph and its consequences

DOI10.1016/S0020-0190(03)00286-2zbMath1161.68647OpenAlexW2052803891MaRDI QIDQ1014419

L. Sunil Chandran, C. R. Subramanian

Publication date: 28 April 2009

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00286-2

zbMATH Keywords

hypercubeeigenvaluetreewidthcombinatorial problemsgraph minorLaplacian matrixchordless cycle

Mathematics Subject Classification ID

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

Related Items (6)

Random subgraphs of the 2D Hamming graph: The supercritical phase ⋮ Differential geometric treewidth estimation in adiabatic quantum computation ⋮ A combinatorial Li-Yau inequality and rational points on curves ⋮ Treewidth computations. II. Lower bounds ⋮ The carving-width of generalized hypercubes ⋮ On the maximum cardinality search lower bound for treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Spectral partitioning works: planar graphs and finite element meshes
• Graph minors. I. Excluding a forest
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Eigenvalues and expanders
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Eigenvalues, diameter, and mean distance in graphs
• Treewidth for graphs with small chordality
• Graph minors. II. Algorithmic aspects of tree-width
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: A spectral lower bound for the treewidth of a graph and its consequences