Tree-width, clique-minors, and eigenvalues.
type: Item
instance of: scholarly article
title: Tree-width, clique-minors, and eigenvalues.
zbMATH Open document ID: 1033.05071
DOI: 10.1016/S0012-365X(03)00199-7
author: Yuan Hong
published in: Discrete Mathematics
publication date: 2004-01-26T00:00:00Z
review text: Let \(G\) be a simple graph of order \(n\). Let \(\rho(G)\) be the spectral radius of \(G\) and let \(\lambda(G)\) be the least eigenvalue of \(G\). The author proves the following results: If \(G\) is \(K_5\) minor-free graph, then \(\rho(G) \leq 1 + \sqrt{3n - 8}\), where equality holds if and only if \(G\) is isomorphic to \(K_3 \nabla (n-3)K_1\); and if \(G\) is \(K_5\) minor-free graph with \(n\geq 5\) vertices, then \(\lambda(G) \geq -\sqrt{3n - 9}\), where equality holds if and only if \(G\) is isomorphic to \(K_{3,n-3}\).
reviewed by: Mirko Lepović
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C83
zbMATH DE Number: 2032867
zbMATH Keywords: graph minor
zbMATH Keywords: tree-width
zbMATH Keywords: surface
zbMATH Keywords: eigenvalue
MaRDI profile type: Publication
cites work: Characterization and Recognition of Partial 3-Trees
cites work: Q5422499
cites work: Q4327350
cites work: Surfaces, tree-width, clique-minors, and partitions
cites work: Sharp lower bounds of the least eigenvalue of planar graphs
cites work: A sharp upper bound of the spectral radius of graphs
cites work: Q4871753
cites work: Über eine Eigenschaft der ebenen Komplexe
full work available at URL: s0012-365x(03)00199-7
OpenAlex ID: W1996839104
Recommended article: Multiplicities of eigenvalues and tree-width of graphs
Recommended article: Graph minors. II. Algorithmic aspects of tree-width
Recommended article: Linear rank-width and linear clique-width of trees
Recommended article: Linear Rank-Width and Linear Clique-Width of Trees
Recommended article: Tree-Related Widths of Graphs and Hypergraphs
Recommended article: From tree-decompositions to clique-width terms
Recommended article: Tree-depth and vertex-minors
Recommended article: Graph-Theoretic Concepts in Computer Science
Recommended article: The Clique-Width of Tree-Power and Leaf-Power Graphs
Recommended article: Spanning trees and even integer eigenvalues of graphs
description: scientific article; zbMATH DE number 2032867