Mysteries around the graph Laplacian eigenvalue 4. (English) Zbl 1262.05102

Summary: We describe our current understanding on the phase transition phenomenon associated with the graph Laplacian eigenvalue \(\lambda =4\) on trees: eigenvectors for \(\lambda <4\) oscillate semi-globally while those for \(\lambda >4\) are concentrated around junctions. For starlike trees, we obtain a complete understanding of this phenomenon. For general graphs, we prove the number of \(\lambda >4\) is bounded from above by the number of vertices with degrees higher than 2; and if a graph contains a branching path, then the eigencomponents for \(\lambda >4\) decay exponentially from the branching vertex toward the leaf.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI arXiv


[1] Bıyıkoğlu, T.; Leydold, J.; Stadler, P. F., Laplacian eigenvectors of graphs, Lecture Notes in Mathematics, vol. 1915, (2007), Springer New York · Zbl 1129.05001
[2] Burden, R. L.; Hedstrom, G. W., The distribution of the eigenvalues of the discrete Laplacian, BIT, 12, 475-488, (1972) · Zbl 0258.65106
[3] Das, K. C., Some spectral properties of the Laplacian matrix of starlike trees, Ital. J. Pure Appl. Math., 21, 197-210, (2007) · Zbl 1166.05304
[4] Das, K. C., A characterization on graphs which achieve the upper bound for the largest Laplacian eigenvalue of graphs, Linear Algebra Appl., 376, 173-186, (2004) · Zbl 1042.05059
[5] Davis, C.; Kahan, W. M., The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal., 7, 1-46, (1970) · Zbl 0198.47201
[6] Golub, G. H.; Van Loan, C. F., Matrix computations, (1996), The Johns Hopkins Univ. Press Baltimore, MD · Zbl 0865.65009
[7] Grone, R.; Merris, R., The Laplacian spectrum of a graph II, SIAM J. Discrete Math., 7, 221-229, (1994) · Zbl 0795.05092
[8] Grone, R.; Merris, R.; Sunder, V. S., The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl., 11, 218-238, (1990) · Zbl 0733.05060
[9] Guo, J. M., The kth Laplacian eigenvalue of a tree, J. Graph Theory, 54, 51-57, (2007) · Zbl 1110.05061
[10] Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197/198, 143-176, (1994) · Zbl 0802.05053
[11] Saito, N.; Woei, E., Analysis of neuronal dendrite patterns using eigenvalues of graph Laplacians, Japan SIAM Lett., 1, 13-16, (2009), (Invited paper) · Zbl 1275.92010
[12] Saito, N.; Woei, E., On the phase transition phenomenon of graph Laplacian eigenfunctions on trees, RIMS Kokyuroku, 1743, 77-90, (2011)
[13] Stevanović, D., Bounding the largest eigenvalue of trees in terms of the largest vertex degree, Linear Algebra Appl., 360, 35-42, (2003) · Zbl 1028.05062
[14] Strang, G., The discrete cosine transform, SIAM Rev., 41, 135-147, (1999) · Zbl 0939.42021
[15] Varga, R. S., Geršgorin and his circles, (2004), Springer New York · Zbl 1057.15023
[16] E. Woei, Characterization and Clustering of Dendritic Trees using Morphological Features extracted by Graph Spectra, Ph.D. dissertation, Dept. Math., Univ. California, Davis, 20.
[17] Zhang, X.-D.; Luo, R., The spectral radius of triangle-free graphs, Australas. J. Combin., 26, 33-39, (2002) · Zbl 1008.05089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.