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.

Page view(s)

75
checked on May 26, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.