×

Counting spanning trees in prism and anti-prism graphs. (English) Zbl 1463.05287

Summary: In this paper, we calculate the number of spanning trees in prism and antiprism graphs corresponding to the skeleton of a prism and an antiprism. By the electrically equivalent transformations and rules of weighted generating function, we obtain a relationship for the weighted number of spanning trees at the successive two generations. Using the knowledge of difference equations, we derive the analytical expressions for enumeration of spanning trees. In addition, we again calculate the number of spanning trees in Apollonian networks, which shows that this method is simple and effective. Finally we compare the entropy of our networks with other studied networks and find that the entropy of the antiprism graph is larger.

MSC:

05C30 Enumeration in graph theory
05C63 Infinite graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Burton and R. Pemantle,Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab., · Zbl 0785.60007
[2] F. Boesch and Z.R. Bogdanowicz,The number of spanning trees in a prism, Int. J. Comput. Math., 21(1987), 229-243. · Zbl 0682.05029
[3] F. Comellas, A. Miralles, H.X. Liu and Z.Z. Zhang,The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs, · Zbl 1395.05157
[4] S.C. Chang, L.C. Chen and W.S. Yang,Spanning trees on the Sierpinski gasket, J. Stat. Phys., 126(2007), 649-667. · Zbl 1110.82007
[5] D. Dhar and A. Dhar,Distribution of sizes of erased loops for loop-erased random walks, Phys. Rev. E, 55(1997), 2093-2096.
[6] D. D’Angeli and A. Donno,Weighted spanning trees on some self-similar graphs, Electron. J. Comb., 18(2011), 16-43.
[7] Q.Y. Ding, W.G. Sun and F.Y. Chen,Applcations of laplcian spectra on a 3-prism graph, Mod. Phys. Lett. B, 28(2014), 1450009.
[8] R. Frucht, J.E. Graver and M.E. Watkins,The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc., 70(1971), 211-218. · Zbl 0221.05069
[9] K.I. Goh, G. Salvi, B. Kahng and D. Kim,Skeleton and fractal scaling in complex networks, Phys. Rev. Lett., 96(2006), 018701.
[10] G. Godsil, G. Royle,Algebraic Graph Theory, Springer, New York, 2001. · Zbl 0968.05002
[11] J.S. Kim, K.I. Goh, G. Salvi, E. Oh, B. Kahng and D. Kim,Fractality in complex networks: Critical and supercritical skeletons, Phys. Rev. E, 75(2007), 016110.
[12] R. Lyons,Asymptotic enumeration of spanning Trees, Combin. Probab. Comput., 14(2005), 491-522. · Zbl 1076.05007
[13] Y. Lin, B. Wu, Z.Z. Zhang and G.R. Chen,Counting spanning trees in selfsimilar networks by evaluating determinants, J. Math. Phys., 52(2011), 113303. · Zbl 1272.05187
[14] S.N. Majumdar and D. Dhar,Equivalence between the Abelian sandpile model and theq→0limit of the Potts model, Phys. A, 185(1992), 129-145.
[15] J.D. Noh and H. Rieger,Random walks on complex networks, Phys. Rev. Lett., 92(2004), 118701.
[16] S.D. Nikolopoulos and C. Papadopoulos,The number of spanning trees inKncomplements of quasi-threshold graphs, Graph Combinator, 20(2004), 383-397. · Zbl 1054.05058
[17] R.M. Ramos, S. Alonso, J. Sicilia and C. Gonzlez,The problem of the optimal biobjective spanning tree, Eur. J. Oper. Res., 111(1998), 617-628. · Zbl 0937.90112
[18] R. Shrock, F.Y. Wu, J,Spanning trees on graphs and lattices in d-dimensions, J. Phys. A, 33(2000), 3881-3902. · Zbl 0949.05041
[19] W.J. Tseng and F.Y. Wu,Dimers on a simple-quartic net with a vacancy, J. Stat. Phys., 110(2003), 671-689. · Zbl 1014.82007
[20] E. Teufl and S. Wagner,The number of spanning trees in self-similar graphs, Ann. Comb., 15(2011), 355-380. · Zbl 1234.05123
[21] E. Teufl and S. Wagner,Determinant identities for Laplace matrices, Linear Algebra Appl., 432(2010), 441-457. · Zbl 1184.15006
[22] E. Teufl and S. Wagner,On the number of spanning trees on various lattices, J. Phys. A, 43 (2010), 415001. · Zbl 1251.05080
[23] F.Y. Wu,The Potts model, Rev. Mod. Phys., 54(1982), 235-268.
[24] B.Y. Wu and K.M. Chao,Spanning Trees and Optimization Problems, Chapman & Hall, FL, 2004. · Zbl 1072.90047
[25] Y.Z. Xiao, H.X. Zhao, G.N. Hu and X.J. Ma,Enumeration of spanning trees in planar unclustered networks, Phys. A, 406(2014), 236-243. · Zbl 1395.05164
[26] Z.Z. Zhang, X.H. Lin, B. Wu and T. Zou,Spanning trees in a fractal scale-free lattice, Phys. Rev. E, 83(2011), 016116.
[27] Z.Z. Zhang, B. Wu and F. Comellas,The number of spanning trees in Apollonian networks, Discrete Appl. Math., 169(2014), 206-213. · Zbl 1288.05066
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.