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

Nakatsukasa, Yuji; Saito, Naoki; Woei, Ernest

Linear Algebra Appl. 438, No. 8, 3231-3246 (2013).

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.

MSC:

05C50

Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

graph Laplacian; localization of eigenvectors; phase transition phenomena; starlike trees; dendritic trees; Gerschgorin’s disks

References:

[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