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.
Keywords:  adjacency matrix; Laplacian matrix; normalized adjacency matrix; spectral radius; algebraic connectivity; Randić index
Classification MSC:  05C50
DOI:  10.21136/CMJ.2020.0290-19

PDF available at:  Springer   Institute of Mathematics CAS

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

Affiliations:   Ranjit Mehatari, Department of Mathematics, National Institute of Technology Rourkela, Rourkela, 769008, India, e-mail: ranjitmehatari@gmail.com, mehatarir@nitrkl.ac.in; M. Rajesh Kannan (corresponding author), Department of Mathematics, Indian Institute of Technology Kharagpur, Kharagpur, West Bengal 721302, India, e-mail: rajeshkannan1.m@gmail.com, rajeshkannan@maths.iitkgp.ac.in


 
PDF available at: