On a Spectral Lower Bound of Treewidth

DOI Web Site
  • GIMA Tatsuya
    Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
  • HANAKA Tesshu
    Department of Informatics, Faculty of Information Science and Electrical Engineering, Kyushu University
  • NORO Kohei
    Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
  • ONO Hirotaka
    Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
  • OTACHI Yota
    Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University

Description

<p>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)].</p>

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top