Spectral ordering of trees with small index. (English) Zbl 1441.05133
Three ordering relations for indices of certain families of trees are established confirming several conjectures. In particular, the first 8 trees of even order with largest index are described. The main tool is a specific diagonalization algorithm for the matrix \(A(T)+\alpha I\), where \(A(T)\) is the adjacency matrix of a tree \(T\) and \(\alpha\in\mathbb{R}\).
Reviewer: Andriy Prymak (Winnipeg)
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
References:
| [1] | Belardo, F.; Li Marzi, E. M.; Simić, S. K., Some notes on graphs whose index is close to 2, Linear Algebra Appl., 423, 81-89 (2007) · Zbl 1114.05056 |
| [2] | Belardo, F.; Li Marzi, E. M.; Simić, S. K., Ordering graphs with index in the interval \((2, \sqrt{2 + \sqrt{5}})\), Discrete Appl. Math., 156, 1670-1682 (2008) · Zbl 1152.05347 |
| [3] | Brouwer, A. E.; Neumaier, A., The graphs with spectral radius between 2 and \(\sqrt{2 + \sqrt{5}} \), Linear Algebra Appl., 114/115, 273-276 (1989) · Zbl 0678.05038 |
| [4] | Collatz, L.; Sinogowitz, U., Spektren endlicher Grafen, Abh. Math. Sem. Univ. Habary, 21, 63-77 (1957) · Zbl 0077.36704 |
| [5] | Cvektović, D.; Doob, M.; Gutman, I., On graphs whose eigenvalues do not exceed \(\sqrt{2 + \sqrt{5}} \), Ars Combin., 14, 225-239 (1982) · Zbl 0504.05040 |
| [6] | Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs: Theory and Applications (1995), Johann Ambrosius Barth: Johann Ambrosius Barth Heidelberg · Zbl 0824.05046 |
| [7] | Cvetković, D.; Rowlinson, P., The largest eigenvalue of a graph: a survey, Linear Multilinear Algebra, 28, 3-33 (1990) · Zbl 0744.05031 |
| [8] | Cvetković, D.; Rowlinson, P.; Simić, S., Eigenspaces of Graphs (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0878.05057 |
| [9] | Ghareghani, N.; Omidi, G. R.; Tayfeh-Rezaie, B., Spectral characterization of graphs with index at most \(\sqrt{2 + \sqrt{5}} \), Linear Algebra Appl., 420, 483-489 (2007) · Zbl 1107.05058 |
| [10] | Goodman, F.; de la Harpe, P.; Jones, V., Matrices over natural numbers: values of the norms, classification, and variations, (Coxeter Graphs and Towers of Algebras. Coxeter Graphs and Towers of Algebras, Mathematical Sciences Research Institute Publications, vol. 14 (1989), Springer-Verlag: Springer-Verlag New York), Chapter 1 · Zbl 0698.46050 |
| [11] | Hoffman, A. J., On limit points of spectral radii of non-negative symmetric integral matrices, Graph Theory Appl., Lect. Notes Math., 303, 165-172 (1972) · Zbl 0297.15016 |
| [12] | Hoffman, A. J.; Smith, J. H., On the spectral radii of topologically equivalent graphs, (Fiedler, M., Recent Advances in Graph Theory (1975), Academia Praha: Academia Praha Prague), 273-281 · Zbl 0327.05125 |
| [13] | Jacobs, D. P.; Trevisan, V., Locating the eigenvalues of trees, Linear Algebra Appl., 434, 81-88 (2011) · Zbl 1231.05167 |
| [14] | Oliveira, E. R.; Stevanović, D.; Trevisan, V., Spectral radius ordering of starlike trees, Linear Multilinear Algebra (2018), in press |
| [15] | Shearer, J., On the distribution of the maximum eigenvalue of graphs, Linear Algebra Appl., 113/114, 17-21 (1989) · Zbl 0672.05059 |
| [16] | Stevanović, D., Spectral Radius of Graphs (2014), Academic Press, Oxford Elsevier LTD |
| [17] | Zhang, F.; Chen, Z., Ordering graphs with small index and its application, Discrete Appl. Math., 121, 295-306 (2002) · Zbl 1003.05099 |
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.
