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

説明

<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>

収録刊行物

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ