×

The normalized Laplacian spectrum of subdivisions of a graph. (English) Zbl 1410.05144

Summary: Determining and analyzing the spectra of graphs is an important and exciting research topic in mathematics science and theoretical computer science. The eigenvalues of the normalized Laplacian of a graph provide information on its structural properties and also on some relevant dynamical aspects, in particular those related to random walks. In this paper, we give the spectra of the normalized Laplacian of iterated subdivisions of simple connected graphs. As an example of application of these results, we find the exact values of their multiplicative degree-Kirchhoff index, Kemeny’s constant and number of spanning trees.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Dasgupta, A.; Hopcroft, J. E.; McSherry, F., Spectral analysis of random graphs with skewed degree distributions, Proceedings of the Forty Fifth Annual IEEE Symposium on Foundations of Computer Science, 602-610 (2004)
[2] Spielman, D. A., Spectral graph theory and its applications, Proceedings of the Forty Eighth Annual IEEE Symposium on Foundations of Computer Science, 29-38 (2007)
[3] Tran, L. V.; Vu, V. H.; Wang, K., Sparse random graphs: Eigenvalues and eigenvectors, Random Struct. Algorithms, 42, 110-134 (2013) · Zbl 1257.05089
[4] Cvetković, D.; Simić, S., Graph spectra in computer science, Linear Algebra Appl., 434, 1545-1562 (2011) · Zbl 1207.68230
[5] Arsić, B.; Cvetković, D.; Simić, S. K.; Škarić, M., Graph spectral techniques in computer sciences, Appl. Anal. Discret. Math., 6, 1-30 (2012) · Zbl 1289.05266
[6] Godsil, C. D.; Royle, G., Algebraic graph theory, Graduate Texts in Mathematics (2001), Springer: Springer New York
[7] Chung, F. R., Spectral Graph Theory (1997), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0867.05046
[8] Brouwer, A. E.; Haemers, W. H., Spectra of graphs, Universitext (2012), Springer: Springer New York · Zbl 1231.05001
[9] Lovász, L., Random walks on graphs: a survey, (Miklós, D.; Sós, V. T.; Szönyi, T., Combinatorics: Paul Erdös is Eighty, vol. 2 (1993), János Bolyai Mathematical Society: János Bolyai Mathematical Society Budapest), 1-46
[10] Zhang, Z.; Shan, T.; Chen, G., Random walks on weighted networks, Phys. Rev. E, 87, 012112 (2013)
[11] Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1976), Springer: Springer New York · Zbl 0328.60035
[12] Levene, M.; Loizou, G., Kemeny’s constant and the random surfer, Am. Math. Mon., 109, 741-745 (2002) · Zbl 1023.60061
[13] Chen, G.; Davis, G.; Hall, F.; Li, Z.; Patel, K.; Stewart, M., An interlacing result on normalized Laplacians, SIAM J. Discret. Math., 18, 353-361 (2004) · Zbl 1079.05054
[14] Blumen, A.; Jurjiu, A.; Koslowski, T.; von Ferber, C., Dynamics of Vicsek fractals, models for hyperbranched polymers, Phys. Rev. E, 67, 061103 (2003)
[15] Butler, S., Algebraic aspects of the normalized Laplacian, Recent Trends in Combinatorics. Recent Trends in Combinatorics, The IMA Volumes in Mathematics and its Applications (2016), IMA · Zbl 1354.05079
[16] Klein, D. J.; Randić, M., Resistance distance, J. Math. Chem., 12, 81-95 (1993)
[17] Chen, H.; Zhang, F., Resistance distance and the normalized Laplacian spectrum, Discret. Appl. Math., 155, 654-661 (2007) · Zbl 1113.05062
[18] Bonchev, D.; Balaban, A. T.; Liu, X.; Klein, D. J., Molecular cyclicity and centricity of polycyclic graphs. I. Cyclicity based on resistance distances or reciprocal distances, Int. J. Quantum Chem., 50, 1-20 (1994)
[19] Hunter, J. J., The role of Kemeny’s constant in properties of Markov chains, Commun. Stat. Theor. Methods, 43, 1309-1321 (2014) · Zbl 1398.60083
[20] Friedland, S.; Gaubert, S.; Han, L., Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl., 438, 738-749 (2013) · Zbl 1261.15039
[21] Asratian, A. S.; Denley, T. M.; Häggkvist, R., Bipartite Graphs and Their Applications, vol. 131 (1998), Cambridge University Press · Zbl 0914.05049
[22] Zhang, X.-D., The smallest eigenvalue for reversible Markov chains, Linear Algebra Appl., 383, 175-186 (2004) · Zbl 1043.60057
[23] Diaconis, P.; Stroock, D., Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab., 36-61 (1991) · Zbl 0731.60061
[24] Bajorin, N.; Chen, T.; Dagan, A.; Emmons, C.; Hussein, M.; Khalil, M.; Mody, P.; Steinhurst, B.; Teplyaev, A., Vibration modes of 3n-gaskets and other fractals, J. Phys. A Math. Theor., 41, 015101 (2008) · Zbl 1181.28007
[25] Teplyaev, A., Spectral analysis on infinite Sierpiński gaskets, J. Funct. Anal., 159, 537-567 (1998) · Zbl 0924.58104
[26] Yang, Y.; Klein, D. J., Resistance distance-based graph invariants of subdivisions and triangulations of graphs, Discret. Appl. Math., 181, 260-274 (2015) · Zbl 1304.05040
[27] Xie, P.; Lin, Y.; Zhang, Z., Spectrum of walk matrix for Koch network and its application, J. Chem. Phys., 142, 224106 (2015)
[28] Zhang, Z.; Guo, X.; Lin, Y., Full eigenvalues of the Markov matrix for scale-free polymer networks, Phys. Rev. E, 90, 022816 (2014)
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.