Locating the eigenvalues of trees. (English) Zbl 1231.05167
Summary: We give an \(O(n)\) method that computes, for any tree \(T\) and interval \((\alpha ,\beta )\), how many eigenvalues of \(T\) lie within the interval. Our method is based on Sylvester’s Law of Inertia. We use our algorithm to show that the nonzero eigenvalues of a caterpillar are simple. It follows that caterpillars having \(b\) back nodes, where \(b > 2\sqrt{\Delta -1}\), are not integral. We also show that among the regular caterpillars \(C(b,k)\) formed by adjoining \(k\) legs to each of \(b\) back nodes, all positive roots are in the interval \((\sqrt{k}-1, \sqrt{k}+2)\), and \(C(b,k)\) is not integral if \(b>2\).
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 05C05 | Trees |
References:
| [1] | Bradley, G. L., A Primer of Linear Algebra (1975), Prentice Hall: Prentice Hall Englewood Cliffs · Zbl 0334.15001 |
| [2] | Cao, D.; Yuan, H., The distribution of eigenvalues in graphs, Linear Algebra Appl., 216, 211-224 (1995) · Zbl 0820.05047 |
| [3] | Fürer, M., Efficient computation of the characteristic polynomial of a tree and related tasks, Proc. European Symposium on Algorithms, Springer Verlag, LNCS v, 5757, 11-22 (2009) · Zbl 1256.05232 |
| [4] | Graham, R. L., On a diophantine equation arising in graph theory, European. J. Combin., 1, 107-112 (1980) · Zbl 0453.10013 |
| [5] | Jacobs, D. P.; Trevisan, V., The determinant of a tree’s neighborhood matrix, Linear Algebra Appl., 256, 235-249 (1997) · Zbl 0916.05051 |
| [6] | Jacobs, D. P.; Machado, C. M.S.; Trevisan, V., An \(O(n^2)\) algorithm for the characteristic polynomial of a tree, J. Combin. Math. Combin. Comput., 54, 213-221 (2005) · Zbl 1080.05089 |
| [7] | Krivelevich, M.; Sudakov, B., The largest eigenvalue of sparse random graphs, Combin. Probab. Comput., 12, 61-72 (2003) · Zbl 1012.05109 |
| [8] | Nedela, R.; Hı´c, P. P., Balanced integral trees, Math. Slovaca, 48, 5, 429-445 (1998) · Zbl 0958.05025 |
| [9] | Rojo, O.; Soto, R., The spectra of the adjacency matrix and Laplacian matrix for some balanced trees, Linear Algebra Appl., 403, 97-117 (2005) · Zbl 1069.05047 |
| [10] | Rojo, O., The spectra of some trees and bounds for the largest eigenvalue of any tree, Linear Algebra Appl., 414, 199-217 (2006) · Zbl 1092.05047 |
| [11] | L. Wang, Integral trees and integral graphs, Doctoral Thesis, Universiteit Twente, 2005.; L. Wang, Integral trees and integral graphs, Doctoral Thesis, Universiteit Twente, 2005. |
| [12] | Watanabe, M.; Schwenk, A. J., Integral starlike trees, J. Austral. Math. Soc. Ser. A, 28, 120-128 (1979) · Zbl 0428.05021 |
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.
