Bounding the largest eigenvalue of trees in terms of the largest vertex degree. (English) Zbl 1028.05062
Let \(\lambda_1(G)\) denote the largest eigenvalue of the adjacency matrix and let \(\mu_1(G)\) denote the largest eigenvalue of the Laplacian matrix \(L(G)= QQ^t\) of a graph \(G\) (\(Q\) is an incidence matrix of \(G\)). The author shows that if a tree \(T\) has the largest vertex degree \(\Delta\) then \(\lambda_1(T)< 2\sqrt{\Delta- 1}\) and \(\mu_1(T)< \Delta+ 2\sqrt{\Delta-1}\).
Reviewer: Alexander Rappoport (Moskva)
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
References:
| [1] | Anderson, W. N.; Morley, T. D., Eigenvalues of the Laplacian of a graph, Linear and Multilinear Algebra, 18, 141-145 (1985) · Zbl 0594.05046 |
| [2] | Biggs, N., Algebraic Graph Theory (1974), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0284.05101 |
| [3] | Cvetković, D.; Doob, M.; Sachs, H., Spectra of graphs-theory and application (1995), Johann Ambrosius Barth Verlag: Johann Ambrosius Barth Verlag Heidelberg-Leipzig · Zbl 0824.05046 |
| [4] | Cvetković, D.; Rowlinson, P., The largest eigenvalue of a graph: a survey, Linear and Multilinear Algebra, 28, 3-33 (1990) · Zbl 0744.05031 |
| [5] | Godsil, C. D., Spectra of trees, Annals of Discrete Mathematics, 20, 151-159 (1984) · Zbl 0559.05040 |
| [6] | Godsil, C. D.; Gutman, I., Wiener index, graph spectrum, line graph, ACH Models Chem., 136, 503-510 (1999) |
| [7] | Grone, R.; Merris, R., The Laplacian spectrum of a graph (II), SIAM J. Discrete Math., 7, 221-229 (1994) · Zbl 0795.05092 |
| [8] | Heilmann, O. J.; Lieb, E. H., Theory of monomer-dimer systems, Commun. Math. Phys., 25, 190-232 (1972) · Zbl 0228.05131 |
| [9] | Lovász, L.; Pelikan, J., On the eigenvalues of trees, Periodica Math. Hung., 3, 175-182 (1973) · Zbl 0247.05108 |
| [10] | Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197, 198, 143-176 (1994) · Zbl 0802.05053 |
| [11] | Shu, J. L.; Hong, Y.; Wen-Ren, K., A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph, Linear Algebra Appl., 347, 123-129 (2002) · Zbl 0999.05073 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
