×

On the \(A_{\alpha}\)-spectra of trees. (English) Zbl 1357.05089

Summary: Let \(G\) be a graph with adjacency matrix \(A(G)\) and let \(D(G)\) be the diagonal matrix of the degrees of \(G\). For every real \(\alpha \in [0, 1]\), define the matrix \(A_\alpha(G)\) as \[ A_\alpha(G) = \alpha D(G) +(1 - \alpha) A(G) . \] This paper gives several results about the \(A_\alpha\)-matrices of trees. In particular, it is shown that if \(T_{\operatorname{\Delta}}\) is a tree of maximal degree {\(\Delta\)}, then the spectral radius of \(A_\alpha(T_{\operatorname{\Delta}})\) satisfies the tight inequality \[ \rho(A_\alpha(T_{\operatorname{\Delta}})) < \alpha \operatorname{\Delta} + 2(1 - \alpha) \sqrt{\operatorname{\Delta} - 1}, \] which implies previous bounds of C. D. Godsil [Ann. Discrete Math. 20, 151–159 (1984; Zbl 0559.05040)], L. Lovász [Combinatorial problems and exercises. 2. ed. Amsterdam: North-Holland. (1993; Zbl 0785.05001)], and D. Stevanović [Linear Algebra Appl. 360, 35–42 (2003; Zbl 1028.05062)]. The proof is deduced from some new results about the \(A_\alpha\)-matrices of Bethe trees and generalized Bethe trees. In addition, several bounds on the spectral radius of \(A_\alpha\) of general graphs are proved, implying tight bounds for paths and Bethe trees.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C05 Trees
15A18 Eigenvalues, singular values, and eigenvectors

References:

[1] Chen, Y., Properties of spectra of graphs and line graphs, Appl. Math. J. Chinese Univ. Ser. B, 17, 3, 371-376 (2002) · Zbl 1022.05046
[2] Collatz, L.; Sinogowitz, U., Spektrcn endlicher Graten, Abh. Math. Scm. Univ. Hamburg, 21, 63-77 (1957) · Zbl 0077.36704
[3] Cvetković, D.; Rowlinson, P.; Simić, S., An Introduction to the Theory of Graph Spectra, London Math. Soc. Stud. Texts, vol. 75 (2010), Cambridge, vii+364 pp · Zbl 1211.05002
[4] Godsil, C. D., Spectra of trees, Ann. Discrete Math., 20, 151-159 (1984) · Zbl 0559.05040
[5] Heilmann, O. J.; Lieb, E. H., Theory of monomer-dimer systems, Comm. Math. Phys., 25, 190-232 (1972) · Zbl 0228.05131
[6] Horn, R.; Johnson, C., Matrix Analysis (1985), Cambridge University Press: Cambridge University Press Cambridge, xiii+561 pp · Zbl 0576.15001
[7] Ikebe, Y.; Inagaki, T.; Miyamoto, S., The monotonicity theorem, Cauchy’s interlace theorem, and the Courant-Fischer theorem, Amer. Math. Monthly, 94, 352-354 (1987) · Zbl 0623.15010
[8] Lovász, L., Combinatorial Problems and Exercises (1993), Elsevier: Elsevier Amsterdam, 636 pp · Zbl 0785.05001
[9] Lovász, L.; Pelikán, J., On the eigenvalues of trees, Period. Math. Hungar., 3, 175-182 (1973) · Zbl 0247.05108
[10] Nikiforov, V., Merging the \(A\)- and \(Q\)-spectral theories (2016), Preprint available at · Zbl 1499.05384
[11] 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
[12] Rojo, O.; Robbiano, M., An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalues of any tree, Linear Algebra Appl., 427, 138-150 (2007) · Zbl 1126.05069
[13] Smith, J. H., Some properties of the spectrum of a graph, (Guy, R.; Hanani, H.; Sauer, N.; Schonhcim, J., Combinatorial Structures and Their Applications (1970), Gordon and Breach: Gordon and Breach New York), 403-406 · Zbl 0249.05136
[14] 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
[15] So, W., Commutativity and spectra of Hermitian matrices, Linear Algebra Appl., 212-213, 121-129 (1994) · Zbl 0815.15005
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.