Some results about the connectivity of trees
Open Access
- 1 April 2013
- journal article
- Published by FapUNIFESP (SciELO) in Pesquisa Operacional
- Vol. 33 (1) , 123-132
Abstract
The second smallest Laplacian eigenvalue of a graph G is called algebraic connectivity, denoted a(G). The ordering of trees via this graph invariant is frequently studied in the literature. In this paper, we present a new invariant, the Internal Degree Sequence (IDS), that also supports an accurate evaluation of the connectivity of trees. We compare the IDS with a(G) for all elements in six classes of trees known to have the largest algebraic connectivity and we show that the IDS provides a strict total ordering of the elements of these classes. This result is also proved for a subclass of trees of diameter 4Keywords
This publication has 10 references indexed in Scilit:
- Ordering trees by algebraic connectivityLinear Algebra and its Applications, 2012
- The six classes of trees with the largest algebraic connectivityDiscrete Applied Mathematics, 2008
- Ordering trees with algebraic connectivity and diameterLinear Algebra and its Applications, 2007
- Old and new results on algebraic connectivity of graphsLinear Algebra and its Applications, 2007
- On the two conjectures of GraffitiLinear Algebra and its Applications, 2004
- An upper bound on algebraic connectivity of graphs with many cutpointsThe Electronic Journal of Linear Algebra, 2001
- Extremizing algebraic connectivity subject to graph theoretic constraintsThe Electronic Journal of Linear Algebra, 1998
- Ordering trees by algebraic connectivityGraphs and Combinatorics, 1990
- Algebraic connectivity of treesCzechoslovak Mathematical Journal, 1987
- Algebraic connectivity of graphsCzechoslovak Mathematical Journal, 1973