On a Spectral Lower Bound of Treewidth

Tatsuya Gima; Tesshu Hanaka; Kohei Noro; Hirotaka Ono; Yota Otachi

doi:10.1587/transinf.2023FCL0002

On a Spectral Lower Bound of Treewidth

Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono, Yota Otachi

Mathematical Informatics

Research output: Contribution to journal › Letter › peer-review

1 Citation (Scopus)

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

Original language	English
Pages (from-to)	328-330
Number of pages	3
Journal	IEICE Transactions on Information and Systems
Volume	E107.D
Issue number	3
DOIs	https://doi.org/10.1587/transinf.2023FCL0002
Publication status	Published - Mar 2024

All Science Journal Classification (ASJC) codes

Software
Hardware and Architecture
Computer Vision and Pattern Recognition
Electrical and Electronic Engineering
Artificial Intelligence

Access to Document

10.1587/transinf.2023FCL0002

Cite this

@article{73a416f43ab243858811a0d812c7c9fa,

title = "On a Spectral Lower Bound of Treewidth",

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 = "Laplacian matrix, algebraic connectivity, eigenvalue, treewidth",

author = "Tatsuya Gima and Tesshu Hanaka and Kohei Noro and Hirotaka Ono and Yota Otachi",

note = "Publisher Copyright: Copyright {\textcopyright} 2024 The Institute of Electronics, Information and Communication Engineers.",

year = "2024",

month = mar,

doi = "10.1587/transinf.2023FCL0002",

language = "English",

volume = "E107.D",

pages = "328--330",

journal = "IEICE Transactions on Information and Systems",

issn = "0916-8532",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "3",

}

TY - JOUR

T1 - On a Spectral Lower Bound of Treewidth

AU - Gima, Tatsuya

AU - Hanaka, Tesshu

AU - Noro, Kohei

AU - Ono, Hirotaka

AU - Otachi, Yota

PY - 2024/3

Y1 - 2024/3

N2 - 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)].

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

KW - Laplacian matrix

KW - algebraic connectivity

KW - eigenvalue

KW - treewidth

UR - http://www.scopus.com/inward/record.url?scp=85187101454&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85187101454&partnerID=8YFLogxK

U2 - 10.1587/transinf.2023FCL0002

DO - 10.1587/transinf.2023FCL0002

M3 - Letter

AN - SCOPUS:85187101454

SN - 0916-8532

VL - E107.D

SP - 328

EP - 330

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 3

ER -

On a Spectral Lower Bound of Treewidth

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this