๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Treewidth Lower Bounds with Brambles

โœ Scribed by Hans L. Bodlaender; Alexander Grigoriev; Arie M. C. A. Koster

Book ID
106148791
Publisher
Springer
Year
2007
Tongue
English
Weight
426 KB
Volume
51
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Treewidth computations II. Lower bounds
Treewidth computations II. Lower bounds
โœ Hans L. Bodlaender; Arie M.C.A. Koster ๐Ÿ“‚ Article ๐Ÿ“… 2011 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 335 KB
A spectral lower bound for the treewidth
A spectral lower bound for the treewidth of a graph and its consequences
โœ L.Sunil Chandran; C.R. Subramanian ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 95 KB

We give a lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. We use this lower bound to show that the treewidth of a d-dimensional hypercube is at least 3 We generalize this result to Hamming graphs. We also observe that every graph G on n v