In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].
No takes yet. Share an insight, caveat, or question.
Gima et al. (2024) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: