Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/103399
Title: | Immanant inequalities for Laplacians of trees | Authors: | Chan, O. Lam, T.K. |
Keywords: | Immanants Laplacians of trees Matchings |
Issue Date: | Aug-1999 | Citation: | Chan, O.,Lam, T.K. (1999-08). Immanant inequalities for Laplacians of trees. SIAM Journal on Matrix Analysis and Applications 21 (1) : 129-144. ScholarBank@NUS Repository. | Abstract: | Let Tn be the collection of trees on n vertices. Let Tn (b; p, q), Tn (m; k), and Tn (d; k) be subsets of Tn comprising trees, each whose vertex set has bipartition (p, q), trees whose maximum matching has size k, and trees of diameter k, respectively. Brualdi and Goldwasser [Discrete Math., 48 (1984), pp. 1-21] obtained lower bounds on the permanent of the Laplacian matrix of a tree from each of these subsets. They characterized the tree in each of these subsets whose Laplacian matrix has the smallest permanent as the "double star" in Tn (b; p, q), the "spur" in Tn (m; k), and the "broom" in Tn (d; k). In this work, the concept of vertex orientations and a new interpretation of the matching numbers in a tree allow us to formulate a unified approach to extending these results to all other immanant functions besides the permanent. It turns out that the "double star" and the "spur" remain the tree in Tn (b; p, q) and the tree in Tn (m; k), respectively, whose Laplacian matrix has the smallest immanant value for all immanants. For Tn (d; k) the tree that has the smallest immanant value varies with the immanant function, but it belongs to a small family of "caterpillars" whose legs are all concentrated on a single vertex. | Source Title: | SIAM Journal on Matrix Analysis and Applications | URI: | http://scholarbank.nus.edu.sg/handle/10635/103399 | ISSN: | 08954798 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.