The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Nesta carta, apresentamos um novo limite inferior para a largura da árvore de um gráfico em termos do segundo menor autovalor de sua matriz Laplaciana. Nosso limite melhora ligeiramente o limite inferior dado por Chandran e Subramanian [Inf. Processo. Lett., 87 (2003)].
Tatsuya GIMA
Nagoya University
Tesshu HANAKA
Kyushu University
Kohei NORO
Nagoya University
Hirotaka ONO
Nagoya University
Yota OTACHI
Nagoya University
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.
Copiar
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
Copiar
@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},}
Copiar
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 -