On trees with maximum algebraic connectivity
Open Access
- 1 January 2016
- journal article
- Published by National Library of Serbia in Applicable Analysis and Discrete Mathematics
- Vol. 10 (1) , 88-101
Abstract
In this paper, trees with fixed diameter and any number of vertices are investigated. A subclass of trees with diameter 2k is introduced, the diameter path trees (dp-trees). Two subclasses of dp-trees are defined in which we characterize the elements that maximize the algebraic connectivity. Also, it is proved that if any tree maximizes the algebraic connectivity over all trees with diameter 2k then it is a dp-tree. For such trees, a bound for the degrees of their vertices is given. In the case of the odd diameter, 2k-1, we show that P2k is the only tree that maximizes the algebraic connectivity.Keywords
This publication has 17 references indexed in Scilit:
- Maximizing algebraic connectivity for certain families of graphsLinear Algebra and its Applications, 2015
- Ordering trees and graphs with few cycles by algebraic connectivityLinear Algebra and its Applications, 2014
- Locating the Eigenvalues of TreesLinear Algebra and its Applications, 2011
- Algebraic Connectivity of Connected Graphs with Fixed Number of Pendant VerticesGraphs and Combinatorics, 2010
- An Introduction to the Theory of Graph Spectra2009
- On graphs with algebraic connectivity equal to minimum edge densityLinear Algebra and its Applications, 2003
- Constructions for type I trees with nonisomorphic Perron branchesCzechoslovak Mathematical Journal, 1999
- Tight bounds on the algebraic connectivity of a balanced binary treeThe Electronic Journal of Linear Algebra, 1999
- Extremizing algebraic connectivity subject to graph theoretic constraintsThe Electronic Journal of Linear Algebra, 1998
- Ordering trees by algebraic connectivityGraphs and Combinatorics, 1990