Czechoslovak Mathematical Journal, Vol. 71, No. 1, pp. 231-251, 2021
Eigenvalue bounds for some classes of matrices associated with graphs
Ranjit Mehatari, M. Rajesh Kannan
Received July 1, 2019. Published online September 21, 2020.
Abstract: For a given complex square matrix $A$ with constant row sum, we establish two new eigenvalue inclusion sets. Using these bounds, first, we derive bounds for the second largest and the smallest eigenvalues of adjacency matrices of $k$-regular graphs. Then we establish some bounds for the second largest and the smallest eigenvalues of the normalized adjacency matrices of graphs and the second smallest and the largest eigenvalues of the Laplacian matrices of graphs. The sharpness of these bounds is verified by examples.
References: [1] A. Banerjee, R. Mehatari: An eigenvalue localization theorem for stochastic matrices and its application to Randić matrices. Linear Algebra Appl. 505 (2016), 85-96. DOI 10.1016/j.laa.2016.04.023 | MR 3506485 | Zbl 1338.15069
[2] B. Bollobás, P. Erdös: Graphs of extremal weights. Ars Comb. 50 (1998), 225-233. MR 1670561 | Zbl 0963.05068
[3] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. American Elsevier, New York (1976). MR 0411988 | Zbl 1226.05083
[4] Ş. B. Bozkurt, A. D. Güngör, I. Gutman, A. S. Çevik: Randić matrix and Randić energy. MATCH Commun. Math. Comput. Chem. 64 (2010), 239-250. MR 2677585 | Zbl 1265.05113
[5] A. E. Brouwer, W. H. Haemers: Spectra of Graphs. Universitext. Springer, Berlin (2012). DOI 10.1007/978-1-4614-1939-6 | MR 2882891 | Zbl 1231.05001
[6] S. Butler, F. Chung: Spectral graph theory. Handbook of Linear Algebra (L. Hogben, ed.). Discrete Mathematics and its Applications. CRC Press, Boca Raton (2014), Article ID 47. MR 3013937 | Zbl 1284.15001
[7] M. S. Cavers: The normalized Laplacian matrix and general Randić index of graphs: Ph.D. Thesis. University of Regina, Regina (2010). MR 3078627
[8] F. R. K. Chung: Spectral Graph Theory. Regional Conference Series in Mathematics 92. American Mathematical Society, Providence (1997). MR 1421568 | Zbl 0867.05046
[9] D. Cvetković, M. Doob, H. Sachs: Spectra of Graphs: Theory and Applications. Pure and Applied Mathematics 87. Academic Press, New York (1980). MR 0572262 | Zbl 0458.05042
[10] K. C. Das: A sharp upper bound for the number of spanning trees of a graph. Graphs Comb. 23 (2007), 625-632. DOI 10.1007/s00373-007-0758-4 | MR 2365415 | Zbl 1139.05032
[11] M. Fiedler: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. DOI 10.21136/CMJ.1973.101168 | MR 0318007 | Zbl 0265.05119
[12] J. Li, J-M. Guo, W. C. Shiu: Bounds on normalized Laplacian eigenvalues of graphs. J. Inequal. Appl. 316 (2014), Article ID 316, 8 pages. DOI 10.1186/1029-242X-2014-316 | MR 3344113 | Zbl 1332.05090
[13] R. Marsli, F. J. Hall: On bounding the eigenvalues of matrices with constant row-sums. Linear Multilinear Algebra 67 (2019), 672-684. DOI 10.1080/03081087.2018.1430736 | MR 3914323 | Zbl 1412.15020
[14] M. Randić: Characterization of molecular branching. J. Am. Chem. Soc. 97 (1975), 6609-6615. DOI 10.1021/ja00856a001
[15] O. Rojo, R. L. Soto: A new upper bound on the largest normalized Laplacian eigenvalue. Oper. Matrices 7 (2013), 323-332. DOI 10.7153/oam-07-19 | MR 3099188 | Zbl 1283.05168
[16] Z. Stanić: Inequalities for Graph Eigenvalues. London Mathematical Society Lecture Note Series 423. Cambridge University Press, Cambridge (2015). DOI 10.1017/CBO9781316341308 | MR 3469535 | Zbl 1368.05001
[17] R. S. Varga: Geršgorin and His Circles. Springer Series in Computational Mathematics 36. Springer, Berlin (2004). DOI 10.1007/978-3-642-17798-9 | MR 2093409 | Zbl 1057.15023
[18] H. Wolkowicz, G. P. H. Styan: Bounds for eigenvalues using traces. Linear Algebra Appl. 29 (1980), 471-506. DOI 10.1016/0024-3795(80)90258-X | MR 0562777 | Zbl 0435.15015
