An improved spectral lower bound of treewidth

DOI10.1016/J.IPL.2024.106536MaRDI QIDQ6663525

Kohei Noro, Tesshu Hanaka, Tatsuya Gima, Hirotaka Ono, Yota Otachi

Publication date: 14 January 2025

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

zbMATH Keywords

treewidthLaplacian eigenvalue

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Vertex degrees (05C07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Treewidth computations. II. Lower bounds
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Spectral partitioning works: planar graphs and finite element meshes
• Treewidth computations. I: Upper bounds
• A spectral lower bound for the treewidth of a graph and its consequences
• A partial k-arboretum of graphs with bounded treewidth
• A tight lower bound on the matching number of graphs via Laplacian eigenvalues
• Easy problems for tree-decomposable graphs
• Provably Shorter Regular Expressions from Deterministic Finite Automata
• Eigenvalues of the Laplacian of a graph^∗
• Graph minors. II. Algorithmic aspects of tree-width
• The Laplacian Spectrum of a Graph II

This page was built for publication: An improved spectral lower bound of treewidth

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