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 | Size | Format | |
---|---|---|---|---|
Combinatorial Perron values of trees and bottleneck matrices.pdf | 1.78 MB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.