Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/16673
 Title: Combinatorial Perron values of trees and bottleneck matrices Author: Andrade, EnideDahl, Geir Keywords: Perron valuebottleneck matrixLaplacian matrixMajorization Issue Date: 2017 Publisher: Taylor & Francis Abstract: The algebraic connectivity $a(G)$ of a graph $G$ is an important parameter, defined as the second smallest eigenvalue of the Laplacian matrix of $G$. If $T$ is a tree, $a(T)$ is closely related to the Perron values (spectral radius) of so-called bottleneck matrices of subtrees of $T$. In this setting we introduce a new parameter called the {\em combinatorial Perron value} $\rho_c$. This value is a lower bound on the Perron value of such subtrees; typically $\rho_c$ is a good approximation to $\rho$. We compute exact values of $\rho_c$ for certain special subtrees. Moreover, some results concerning $\rho_c$ when the tree is modified are established, and it is shown that, among trees with given distance vector (from the root), $\rho_c$ is maximized for caterpillars. Peer review: yes URI: http://hdl.handle.net/10773/16673 DOI: 10.1080/03081087.2016.1274363 ISSN: 0308-1087 Appears in Collections: CIDMA - ArtigosOGTCG - Artigos

Files in This Item:
File Description SizeFormat
Combinatorial Perron values of trees and bottleneck matrices.pdf1.78 MBAdobe PDF