Back to Search
Start Over
Tree-width, clique-minors, and eigenvalues
- Source :
- Discrete Mathematics. 274:281-287
- Publication Year :
- 2004
- Publisher :
- Elsevier BV, 2004.
-
Abstract
- Let G be a simple graph with n vertices and tw(G) be the tree-width of G. Let ρ(G) be the spectral radius of G and λ(G) be the smallest eigenvalue of G. The join G∇H of disjoint graphs of G and H is the graph obtained from G+H by joining each vertex of G to each vertex of H. In this paper, several results which are concerned with tree-width, clique-minors, and eigenvalues of graphs are given. In particular, we have(1) If G is K5 minor-free graph, thenρ(G)⩽1+3n−8,where equality holds if and only if G is isomorphic to K3∇(n−3)K1.(2) If G is K5 minor-free graph with n⩾5 vertices, thenλ(G)⩾−3n−9,where equality holds if and only if G is isomorphic to K3,n−3.
Details
- ISSN :
- 0012365X
- Volume :
- 274
- Database :
- OpenAIRE
- Journal :
- Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....4b55bd11c48fd8a4373084a08500495d