The Laplacian Spectrum of the Generalized $n$-Prism Networks

Document Type : Research Paper

Author

Department of Mathematics, Khansar Faculty, University of Isfahan, Iran

Abstract

‎The Laplacian eigenvalues and polynomials of the networks play an essential role in understanding the relations between the topology and the dynamic of networks‎. ‎Generally‎, ‎computation of the Laplacian spectrum of a network is a hard problem and there are just a few classes of graphs with the property that their spectra have been completely computed‎. ‎Laplacian spectrum for $ n$-prism networks was investigated in [Liu et al.‎, ‎Neurocomputing 198 (2016) 69-73]‎. ‎In this paper‎, ‎we give a method for calculating the eigenvalues and characteristic polynomial of the Laplacian matrix of a generalized $n$-prism network‎. ‎We show how such large networks can be constructed from small graphs by using graph products‎. ‎Moreover‎, ‎our results are used to obtain the Kirchhoff index and the number of the spanning trees in the generalized $n$-prism networks‎. ‎We also give some examples of applications‎, ‎that explain the usefulness and efficiency of the proposed method‎.

Keywords

Main Subjects


[1] R. Albert, A. L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (2002) p. 47, https://doi.org/10.1103/RevModPhys.74.47.
[2] M. Newman, A. L. Barabasi and D. J. Watts, The Structure and Dynamics of Networks, Princeton University Press, 2006.
[3] M. De Domenico, A. Solé-Ribalta, E. Cozzo, M. Kivelä, Y. Moreno, M. A. Porter, S. Gómez and A. Arenas, Mathematical formulation of multilayer networks, Phys. Rev. X 3 (2013) p. 041022, https://doi.org/10.1103/PhysRevX.3.041022.
[4] R. Guimera, L. Danon, A. Diaz-Guilera, F. Giralt and A. Arenas, Self-similar community structure in a network of human interactions, Phys. Rev. E 68 (2003) p. 065103, https://doi.org/10.1103/PhysRevE.68.065103.
[5] M. E. J. Newman, The structure and function of complex networks, SIAM Rev. 45 (2003) 167–256, https://doi.org/10.1137/S003614450342480.
[6] P. V. Mieghem, Graph Spectra for Complex Networks, Cambridge University Press, 2011.
[7] W. N. Anderson Jr and T. D. Morley, Eigenvalues of the Laplacian of a graph, Linear Multilinear Algebra 18 (1985) 141–145, https://doi.org/10.1080/03081088508817681.
[8] B. Y. Hou, H. J. Zhang and L. Liu, Applications of Laplacian spectra for extended Koch networks, Eur. Phys. J. B 85 (2012) 311–317, https://doi.org/10.1140/epjb/e2012-30373-x.
[9] A. N. Samukhin, S. N. Dorogovtsev and J. F. F. Mendes, Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?, Phys. Rev. E 77 (2008) p. 036115, https://doi.org/10.1103/PhysRevE.77.036115.
[10] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Theory and Applications, Third edition. Johann Ambrosius Barth, Heidelberg, 1995.
[11] R. Merris, Laplacian matrices of graphs; a survay, Linear Algebra Appl. 197-198 (1994) 143–176, https://doi.org/10.1016/0024-3795(94)90486-3.
[12] H. R. Ellahi, R. Nasiri, G. H. Fath-Tabar and A. Gholami, The Signless Laplacian Estrada Index of Unicyclic Graphs, Math. Interdisc. Res. 2 (2017) 155–167, https://doi.org/10.22052/MIR.2017.57775.1038.
[13] B. Mohar and S. Poljak, Eigenvalues in combinatorial optimization: in Combinatorial and Graph-Theoretical Problems in Linear Algebra, R. A. Brualdi, S. Friedland, V. Klee, Eds., IMA Volumes in Mathematics and Its Applications, 50, Springer-Verlag, 1993, 107–151.
[14] S. Burcu Bozkurt Altındag, Note on the sum of powers of normalized signless Laplacian eigenvalues of graphs, Math. Interdisc. Res. 4 (2019) 171 –182, https://doi.org/10.22052/MIR.2019.208991.1180.
[15] R. B. Bapat, The Laplacian matrix of a graphs, Math. Student 65 (1996) 214–223.
[16] S. Barik, R. B. Bapat and S. Pati, On the Laplacian spectra of product graphs, Appl. Anal. Discrete Math. 9 (2015) 39–58, https://doi.org/10.2298/AADM150218006B.
[17] J. Liu, J. Cao, A. Alofi, A. Al-Mazrooei and A. Elaiw, Applications of Laplacian spectra for n-prism networks, Neurocomputing 198 (2016) 69–73, https://doi.org/10.1016/j.neucom.2015.06.109.
[18] Q. Ding, W. Sun and F. Chen, Applications of Laplacian spectra on a 3-prism graph, Modern Phys. Lett. B 28 (2014) p. 1450009, https://doi.org/10.1142/S0217984914500092.
[19] Z. Zhang, Some physical and chemical indices of clique-inserted lattices, J. Stat. Mech. Theory Exp. 2013 (2013) p. P10004, https://doi.org/10.1088/1742-5468/2013/10/P10004.
[20] C. J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, New York, 1987.
[21] P. Marchal, Loop-erased random walks, spanning trees and Hamiltonian cycles, Electron. Comm. Probab. 5 (2000) 39–50, https://doi.org/10.1214/ECP.v5-1016.
[22] I. Gutman and B. Mohar, The quasi-Wiener and the Kirchhoff indices coincide, J. Chem. Inf. Comput. Sci. 36 (1996) 982–985, https://doi.org/10.1021/ci960007t.
[23] Y. P. Hong and R. A. Horn and C. R. Johnson, On the reduction of pairs of hermitian or symmetric matrices to diagonal form by congruence, Linear Algebra Appl. 73 (1986) 213–226, https://doi.org/10.1016/0024-3795(86)90241-7.