Construction of Simultaneous Cospectral Graphs for Adjacency, Laplacian and Normalized Laplacian Matrices
Download PDF
Authors: A. DAS AND P. PANIGRAHI
DOI: 10.46793/KgJMat2306.947D
Abstract:
In this paper we construct several classes of non-regular graphs which are co-spectral with respect to all the three matrices, namely, adjacency, Laplacian and normalized Laplacian, and hence we answer a question asked by Butler [?]. We make these constructions starting with two pairs (G1, H1) and (G2, H2) of A-cospectral regular graphs, then considering the subdivision graphs S(Gi) and R-graphs ℛ(Hi), i = 1, 2, and finally making some kind of partial joins between S(G1) and ℛ(G2) and S(H1) and ℛ(H2). Moreover, we determine the number of spanning trees and the Kirchhoff index of the newly constructed graphs.
Keywords:
Adjacency matrix, Laplacian matrix, normalized Laplacian matrix, cospectral graphs.
References:
[1] D. Bonchev, A. T. Balaban, X. Liu and D. J. Klein, Molecular cyclicity and centricity of polycyclic graphs. I. Cyclicity based on resistance distances or reciprocal distances, International Journal of Quantum Chemistry 50(1) (1994), 1–20. https://doi.org/10.1002/qua.560500102
[2] S. Butler, A note about cospectral graphs for the adjacency and normalized Laplacian matrices, Linear and Multilinear Algebra 58(3) (2010), 387–390. https://doi.org/10.1080/03081080902722741
[3] S. Y. Cui and G. X. Tian, The spectrum and the signless Laplacian spectrum of coronae, Linear Algebra Appl. 437(7) (2012), 1692–1703. https://doi.org/10.1016/j.laa.2012.05.019
[4] F. R. K. Chung, Spectral Graph Theory, CBMS. Reg. Conf. Ser. Math. 92, AMS, Providence, RI, 1997.
[5] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs-Theory and Applications, Third edition, Johann Ambrosius Barth, Heidelberg, 1995.
[6] D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2009.
[7] A. Das and P. Panigrahi. Normalized Laplacian spectrum of some subdivision-coronas of two regular graphs, Linear and Multilinear Algebra 65(5) (2017), 962–972. https://doi.org/10.1080/03081087.2016.1217976
[8] C. Godsil and G. Royle, Algebraic Graph Theory, Springer, New York, 2001.
[9] I. Gutman and B. Mohar, The quasi-Wiener and the Kirchhoff indices coincide, Journal of Chemical Information and Computer Sciences 36(5) (1996), 982–985. https://doi.org/10.1021/ci960007t
[10] D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), 81–95.
[11] X. Liu and P. Lu, Spectra of the subdivision-vertex and subdivision-edge neighbourhood coronae, Linear Algebra Appl. 438(8) (2013), 3547–3559. https://doi.org/10.1016/j.laa.2012.12.033
[12] X. G. Liu and Z. H. Zhang, Spectra of subdivision-vertex and subdivision-edge joins of graphs, Bull. Malays. Math. Sci. Soc. 42 (2019), 15–31. https://doi.org/10.1007/s40840-017-0466-z
[13] C. McLeman and E. McNicholas, Spectra of coronae, Linear Algebra Appl. 435(5) (2011), 998–1007. https://doi.org/10.1016/j.laa.2011.02.007
[14] E. R. van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373(1) (2003), 241–272. https://doi.org/10.1016/S0024-3795(03)00483-X
Login:
