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, Enide
Dahl, Geir
Keywords: Perron value
bottleneck matrix
Laplacian matrix
Majorization
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 - Artigos
OGTCG - Artigos

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


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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