Algebraic connectivity of weighted trees under perturbation |
| |
Authors: | Steve Kirkland Michael Neumann |
| |
Institution: |
a Department of Mathematics and Statistics, University of Regina, Regina, Canada
b Department of Mathematics, University of Connecticut, Storrs, Connecticut, U. S. A. |
| |
Abstract: | We investigate how the algebraic connectivity of a weighted tree behaves when the tree is perturbed by removing one of its branches and replacing it with another. This leads to a number of results, for example the facts that replacing a branch in an unweighted tree by a star on the same number of vertices will not decrease the algebraic connectivity, while replacing a certain branch by a path on the same number of vertices will not increase the algebraic connectivity. We also discuss how the arrangement of the weights on the edges of a tree affects the algebraic connectivity, and we produce a lower bound on the algebraic connectivity of any unweighted graph in terms of the diameter and the number of vertices. Throughout, our techniques exploit a connection between the algebraic connectivity of a weighted tree and certain positive matrices associated with the tree. |
| |
Keywords: | Laplacian Matrix Tree Algebraic Connectivity Perron value |
本文献已被 InformaWorld 等数据库收录! |
|