Algebraic connectivity of trees
The Laplacian matrix of a tree T is \(L(T)=(a_{ij})\), where \(a_{ij}=\deg (v_ i)\) if \(i=j\), \(a_{ij}=-1\) if \(v_ i\) \(v_ j\) is an edge of T, and \(a_{ij}=0\) otherwise. L(T) is seen to be a positive semidefinite symmetric matrix whose second smallest eigenvalue a(T) satisfies \(0<a(T)\leq 1\), with \(a(T)=1\) if and only if T is the star \(K_{1,n-1}\). This eigenvalue has been called the algebraic connectivity of T. The set of eigenvectors of L(T) corresponding to a(T) may be interpreted as real-valued functions on V; these are known as characteristics valuations of T. The results obtained here all relate to trees for which there is a characteristic valuation f and vertex v such that \(f(v)=0\) (these have been called Type I trees). From work of \textit{M. Fiedler} [ibid. 25, 619-633 (1975; Zbl 0437.15004)], it follows that in a Type I tree there is a unique vertex w, called the characteristic vertex of T, for which every characteristic valuation is zero. The multiplicity of a(T) and a method of pruning and grafting of branches of T are obtained from analysis of the branches at w. Obtaining the ``orbit- partitioned form of L(T) from the automorphism group of T, we can separate the spectrum into symmetric and alternating parts. For Type I trees, analysis of the branches at w allows determination of whether a(T) belongs to the symmetric or alternating part of the spectrum.
- Absolute algebraic connectivity of trees
- Algebraic connectivity and degree sequences of trees
- On trees with maximum algebraic connectivity
- Algebraic connectivity of trees with the maximum degree
- Algebraic connectivity of weighted trees under perturbation
- On connectivities of tree graphs
- The smallest values of algebraic connectivity for trees
- Ordering trees by algebraic connectivity
- Ordering trees by algebraic connectivity
- Connectivity and tree structure in finite graphs
- On the geometry and Laplacian of a graph
- Eigenvalues, diameter, and mean distance in graphs
- Some minimax problems for graphs
- Laplacian matrices of graphs: A survey
- Combinatorial Perron parameters for trees
- On algebraic connectivity and spectral integral variations of graphs
- A tight upper bound on the spectral radius of bottleneck matrices for graphs
- Perron value and moment of rooted trees
- Perron values and classes of trees
- Trees with matrix weights: Laplacian matrix and characteristic-like vertices
- Trees with a large Laplacian eigenvalue multiplicity
- Spectra of graphs resulting from various graph operations and products: a survey
- An upper bound on the algebraic connectivity of outerplanar graphs
- Riordan graphs. II: Spectral properties
- On Laplacian energy of graphs
- The effect on the algebraic connectivity of a tree by grafting or collapsing of edges
- The six classes of trees with the largest algebraic connectivity
- The spectral radius of submatrices of Laplacian matrices for graphs with cut vertices
- Characteristic vertices of weighted trees via perron values
- scientific article; zbMATH DE number 4168710 (Why is no real title available?)
- The influence of Miroslav Fiedler on spectral graph theory
- Comparison between Kirchhoff index and the Laplacian-energy-like invariant
- scientific article; zbMATH DE number 2067822 (Why is no real title available?)
- Minimizing algebraic connectivity over graphs made with some given blocks
- Spectral properties of Pascal graphs
- Absolute algebraic connectivity of trees
- Constructions for type I trees with nonisomorphic Perron branches
- Unicyclic graphs with five Laplacian eigenvalues different from 0 and 1
- On the multiplicity of Laplacian eigenvalues for unicyclic graphs
- Bounds of Laplacian spectrum of graphs based on the domination number
- Characteristic vertices of trees*
- Characteristic vertices of trees*
- Ordering trees by algebraic connectivity
- On singularity and properties of eigenvectors of complex Laplacian matrix of multidigraphs
- About the type of broom trees
- The algebraic connectivity of lollipop graphs
- Algebraic connectivity of connected graphs with fixed number of pendant vertices
- Extreme values of the Fiedler vector on trees
- Some degree sequences are determined by Laplacian spectra of the corresponding graphs
- Bottleneck matrices of maximal outerplanar graphs with isomorphic underlying trees
- Entries of the bottleneck matrices of maximal outerplanar graphs
- On Laplacian energy, Laplacian-energy-like invariant and Kirchhoff index of graphs
- Trees with k switches
- Inverse Fiedler vector problem of a graph
- Lower bounds of the Laplacian spectrum of graphs based on diameter
- On the algebraic connectivity of graphs as a function of genus
- Old and new results on algebraic connectivity of graphs
- Ordering trees with nearly perfect matchings by algebraic connectivity
- A survey of automated conjectures in spectral graph theory
- On conjectures involving second largest signless Laplacian eigenvalue of graphs
- The algebraic connectivity of graphs under perturbation
- A conjecture on the algebraic connectivity of connected graphs with fixed girth
This page was built for publication: Algebraic connectivity of trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729804)