IEICE TRANSACTIONS on Information
On a Spectral Lower Bound of Treewidth
Summary :
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)].
- Publication
- IEICE TRANSACTIONS on Information Vol.E107-D No.3 pp.328-330
- Publication Date
- 2024/03/01
- Publicized
- 2023/06/16
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2023FCL0002
- Type of Manuscript
- Special Section LETTER (Special Section on Foundations of Computer Science — Foundations of Computer Science and their New Trends —)
- Category
Authors
Tatsuya GIMA
Nagoya University
Tesshu HANAKA
Kyushu University
Kohei NORO
Nagoya University
Hirotaka ONO
Nagoya University
Yota OTACHI
Nagoya University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tatsuya GIMA, Tesshu HANAKA, Kohei NORO, Hirotaka ONO, Yota OTACHI, "On a Spectral Lower Bound of Treewidth" in IEICE TRANSACTIONS on Information,
vol. E107-D, no. 3, pp. 328-330, March 2024, doi: 10.1587/transinf.2023FCL0002.
Abstract: 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)].
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2023FCL0002/_p
Copy
@ARTICLE{e107-d_3_328,
author={Tatsuya GIMA, Tesshu HANAKA, Kohei NORO, Hirotaka ONO, Yota OTACHI, },
journal={IEICE TRANSACTIONS on Information},
title={On a Spectral Lower Bound of Treewidth},
year={2024},
volume={E107-D},
number={3},
pages={328-330},
abstract={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)].},
keywords={},
doi={10.1587/transinf.2023FCL0002},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - On a Spectral Lower Bound of Treewidth
T2 - IEICE TRANSACTIONS on Information
SP - 328
EP - 330
AU - Tatsuya GIMA
AU - Tesshu HANAKA
AU - Kohei NORO
AU - Hirotaka ONO
AU - Yota OTACHI
PY - 2024
DO - 10.1587/transinf.2023FCL0002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E107-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2024
AB - 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)].
ER -
English
