2024/04/12 by Tatsuya Gima, Gima, Tatsuya, Tesshu Hanaka +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2404.08520
openalex publication_date 2024/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that for every n-vertex graph with at least one edge, its treewidth is greater than or equal to n λ2 / (Δ+ λ2) - 1, where Δ and λ2 are the maximum degree and the second smallest Laplacian eigenvalue of the graph, respectively. This lower bound improves the one by Chandran and Subramanian [Inf. Process. Lett., 2003] and the subsequent one by the authors of the present paper [IEICE Trans. Inf. Syst., 2024]. The new lower bound is almost tight in the sense that there is an infinite family of graphs such that the lower bound is only 1 less than the treewidth for each graph in the family. Additionally, using similar techniques, we also present a lower bound of treewidth in terms of the largest and the second smallest Laplacian eigenvalues.