Repositório Institucional da Universidade de Aveiro > CIDMA - Centro de Investigação e Desenvolvimento em Matemática e Aplicações > CIDMA - Artigos >
 Combinatorial Perron values of trees and bottleneck matrices
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
authors: Andrade, Enide
Dahl, Geir
keywords: Perron value
bottleneck matrix
Laplacian matrix
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.
URI: http://hdl.handle.net/10773/16673
ISSN: 0308-1087
publisher version/DOI: http://dx.doi.org/10.1080/03081087.2016.1274363
source: Linear and Multilinear Algebra
appears in collectionsCIDMA - Artigos

files in this item

file description sizeformat
Combinatorial Perron values of trees and bottleneck matrices.pdf1.78 MBAdobe PDFview/open
Restrict Access. You can Request a copy!

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


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2