×

On the spectrum of the normalized Laplacian of iterated triangulations of graphs. (English) Zbl 1410.05143

Summary: The eigenvalues of the normalized Laplacian of a graph provide information on its topological and structural characteristics and also on some relevant dynamical aspects, specifically in relation to random walks. In this paper, we determine the spectra of the normalized Laplacian of iterated triangulations of a generic simple connected graph. As an application, we also find closed-forms for 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

References:

[1] 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
[2] Bianchi, M.; Cornaro, A.; Palacios, J. L.; Torriero, A., Bounding the sum of powers of normalized Laplacian eigenvalues of graphs through majorization methods, MATCH Commun. Math. Comput. Chem., 70, 707-716 (2013) · Zbl 1299.05045
[3] 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. Quant. Chem., 50, 1-20 (1994)
[4] Brouwer, A. E.; Haemers, W. H., Spectra of Graphs (Universitext) (2012), Springer: Springer New York · Zbl 1231.05001
[5] Butler, S., Algebraic aspects of the normalized Laplacian, (Beveridge, A.; Griggs, J.; Hogben, L.; Musiker, G.; Tetali, P., Recent Trends in Combinatorics (2015), IMA)
[6] Cavers, M.; Fallat, S.; Kirkland, S., On the normalized Laplacian energy and general Randić index \(R_{- 1}\) of graphs, Linear Algebra Appl., 433, 172-190 (2010) · Zbl 1217.05138
[7] Chen, H.; Zhang, F., Resistance distance and the normalized Laplacian spectrum, Discret. Appl. Math., 155, 654-661 (2007) · Zbl 1113.05062
[8] Chung, F. R., Spectral Graph Theory (1997), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0867.05046
[9] Cohen, R.; Havlin, S., Complex Networks. Structure, Robustness and Function (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1196.05092
[10] Comellas, F.; Fertin, G.; Raspaud, A., Recursive graphs with small-world scale-free properties, Phys. Rev. E, 69, 037104 (2004)
[11] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of graphs: theory and application, Pure and Applied Mathematics: A Series of Monographs and Textbooks, vol. 87 (1980), Academic Press: Academic Press New York · Zbl 0458.05042
[12] Das, K. C.; Gutman, I.; Çevik, A. S.; Zhou, B., On Laplacian energy, MATCH Commun. Math. Comput. Chem., 70, 689-696 (2013) · Zbl 1299.05212
[13] Diaconis, P.; Stroock, D., Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab., 1, 36-61 (1991) · Zbl 0731.60061
[14] Dorogovtsev, S. N.; Goltsev, A.; Mendes, J. F.F., Pseudofractal scale-free web, Phys. Rev. E, 65, 6, 066122 (2002)
[15] Feng, L.; Gutman, I.; Yu, G., Degree Kirchhoff index of unicyclic graphs, MATCH Commun. Math. Comput. Chem., 69, 629-648 (2013) · Zbl 1299.05054
[16] 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
[17] Godsil, C. D.; Royle, G., Algebraic Graph Theory, Graduate Texts in Mathematics (2001), Springer: Springer New York
[18] L. Henneberg, Die Graphische Statik der Starren Systeme, Druck und Verlag von B.G. Teubner, Leipzig und Berlin, 1911.; L. Henneberg, Die Graphische Statik der Starren Systeme, Druck und Verlag von B.G. Teubner, Leipzig und Berlin, 1911.
[19] Huang, J.; Li, S., On the normalised Laplacian spectrum, degree-Kirchhoff index and spanning trees of graphs, Bull. Aust. Math. Soc., 91, 353-367 (2015) · Zbl 1326.05082
[20] Hunter, J. J., The role of Kemeny’s constant in properties of Markov chains, Commun. Stat.: Theory Methods, 43, 1309-1321 (2014) · Zbl 1398.60083
[21] Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1976), Springer: Springer New York · Zbl 0328.60035
[22] Khosravanirad, A., A lower bound for Laplacian Estrada index of a graph, MATCH Commun. Math. Comput. Chem., 70, 175-180 (2013) · Zbl 1299.05222
[23] Klein, D. J.; Randić, M., Resistance distance, J. Math. Chem., 12, 81-95 (1993)
[24] Levene, M.; Loizou, G., Kemeny’s constant and the random surfer, Am. Math. Mon., 109, 741-745 (2002) · Zbl 1023.60061
[25] Li, R., Lower bounds for the Kirchhoff index, MATCH Commun. Math. Comput. Chem., 70, 163-174 (2013) · Zbl 1299.05055
[26] 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
[27] Mehatari, R.; Banerjee, A., Effect on normalized graph Laplacian spectrum by motif attachment and duplication, Appl. Math. Comput., 261, 382-387 (2015) · Zbl 1410.05136
[28] Nadakuditi, R. R.; Newman, M. E.J., Graph spectra and the detectability of community structure in networks, Phys. Rev. Lett., 108, 188701 (2012)
[29] Newman, M., Networks: An Introduction (2010), Oxford University Press
[30] Nixon, A.; Ross, E., One brick at a time: a survey of inductive constructions in rigidity theory, (Connelly, R.; Weiss, A. I.; Whiteley, W., Rigidity and Symmetry (Fields Institute Communications), vol. 70 (2014), Springer), 303-324 · Zbl 1320.52024
[31] Palacios, J. L., Resistance distance in graphs and random walks, Int. J. Quantum Chem., 81, 29-33 (2001)
[32] Palacios, J. L., Upper and lower bounds for the additive degree-Kirchhoff index, MATCH Commun. Math. Comput. Chem., 70, 651-655 (2013) · Zbl 1299.05059
[33] Rosenfeld, V. R.; Klein, D. J., An infinite family of graphs with a facile count of perfect matchings, Discret. Appl. Math., 166, 210-214 (2014) · Zbl 1283.05235
[34] Teplyaev, A., Spectral analysis on infinite Sierpiński gaskets, J. Funct. Anal., 159, 537-567 (1998) · Zbl 0924.58104
[35] Tierney, L., Introduction to general state-space Markov chain theory, Markov Chain Monte Carlo in Practice, 59-74 (1996), Springer: Springer US · Zbl 0849.60072
[36] Van Mieghem, P., Graph Spectra for Complex Networks (2010), Cambridge University Press
[37] 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
[38] Zhang, X.-D., The smallest eigenvalue for reversible Markov chains, Linear Algebra Appl., 383, 175-186 (2004) · Zbl 1043.60057
[39] Zhang, Z.; Lin, Y.; Guo, X., Eigenvalues for the transition matrix of a small-world scale-free network: explicit expressions and applications, Phys. Rev. E, 91, 062808 (2015)
[40] Zhang, Z.; Rong, L.; Zhou, S., A general geometric growth model for pseudofractal scale-free web, Physica A, 377, 329-339 (2007)
[41] Zhang, Z.; Shan, T.; Chen, G., Random walks on weighted networks, Phys. Rev. E, 87, 012112 (2013)
[42] Zhang, Z.; Zhou, S.; Chen, L., Evolving pseudofractal networks, Eur. Phys. J. B, 58, 337-344 (2007)
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.