Title: The Laplacian spectra of graphs with a tree structure
Abstract: Trees are very common in the theory and applications of combinatorics. In this article, we consider graphs whose underlying structure is a tree, except that its vertices are graphs in their own right and where adjacent graphs (vertices) are linked by taking their join. We study the spectral properties of the Laplacian matrices of such graphs. It turns out that in order to capture known spectral properties of the Laplacian matrices of trees, it is necessary to consider the Laplacians of vertex-weighted graphs. We focus on the second smallest eigenvalue of such Laplacians and on the properties of their corresponding eigenvector. We characterize the second smallest eigenvalue in terms of the Perron branches of a tree. Finally, we show that our results are applicable to advancing the solution to the problem of whether there exists a graph on n vertices whose Laplacian has the integer eigenvalues 0, 1, …, n − 1.
Publication Year: 2009
Publication Date: 2009-04-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 15
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot