COUNTING SPANNING TREES IN PRISM AND ANTI-PRISM GRAPHS

Weigang Sun; Shuai Wang; Jingyuan Zhang

doi:10.11948/2016006

2016 Volume 6 Issue 1

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2016 > 6(1): 65-75

Next Article Previous Article

Weigang Sun, Shuai Wang, Jingyuan Zhang. COUNTING SPANNING TREES IN PRISM AND ANTI-PRISM GRAPHS[J]. Journal of Applied Analysis & Computation, 2016, 6(1): 65-75. doi: 10.11948/2016006

Citation:

Weigang Sun, Shuai Wang, Jingyuan Zhang. COUNTING SPANNING TREES IN PRISM AND ANTI-PRISM GRAPHS[J]. Journal of Applied Analysis & Computation, 2016, 6(1): 65-75. doi: 10.11948/2016006

COUNTING SPANNING TREES IN PRISM AND ANTI-PRISM GRAPHS

Department of Mathematics, School of Science, Hangzhou Dianzi University, Hangzhou 310018, China

Fund Project:

Abstract

Abstract

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.
- Electrically equivalent transformation /
- spanning trees /
- prism graph /
- anti-prism graph
MSC: 05C30;05C63;97K30

FullText(HTML)

References

[1]	R. Burton and R. Pemantle, Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab., 21(1993), 1329-1371. Google Scholar
[2]	F. Boesch and Z.R. Bogdanowicz, The number of spanning trees in a prism, Int. J. Comput. Math., 21(1987), 229-243. Google Scholar
[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, Phys. A, 392(2013), 2803-2806. Google Scholar
[4]	S.C. Chang, L.C. Chen and W.S. Yang, Spanning trees on the Sierpinski gasket, J. Stat. Phys., 126(2007), 649-667. Google Scholar
[5]	D. Dhar and A. Dhar, Distribution of sizes of erased loops for loop-erased random walks, Phys. Rev. E, 55(1997), 2093-2096. Google Scholar
[6]	D. D'Angeli and A. Donno, Weighted spanning trees on some self-similar graphs, Electron. J. Comb., 18(2011), 16-43. Google Scholar
[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. Google Scholar
[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. Google Scholar
[9]	K.I. Goh, G. Salvi, B. Kahng and D. Kim, Skeleton and fractal scaling in complex networks, Phys. Rev. Lett., 96(2006), 018701. Google Scholar
[10]	G. Godsil, G. Royle, Algebraic Graph Theory, Springer, New York, 2001. Google Scholar
[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. Google Scholar
[12]	R. Lyons, Asymptotic enumeration of spanning Trees, Combin. Probab. Comput., 14(2005), 491-522. Google Scholar
[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. Google Scholar
[14]	S.N. Majumdar and D. Dhar, Equivalence between the Abelian sandpile model and the q ! 0 limit of the Potts model, Phys. A, 185(1992), 129-145. Google Scholar
[15]	J.D. Noh and H. Rieger, Random walks on complex networks, Phys. Rev. Lett., 92(2004), 118701. Google Scholar
[16]	S.D. Nikolopoulos and C. Papadopoulos, The number of spanning trees in Kncomplements of quasi-threshold graphs, Graph Combinator, 20(2004), 383-397. Google Scholar
[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. Google Scholar
[18]	R. Shrock, F.Y. Wu, J, Spanning trees on graphs and lattices in d-dimensions, J. Phys. A, 33(2000), 3881-3902. Google Scholar
[19]	W.J. Tseng and F.Y. Wu, Dimers on a simple-quartic net with a vacancy, J. Stat. Phys., 110(2003), 671-689. Google Scholar
[20]	E. Teufl and S. Wagner, The number of spanning trees in self-similar graphs, Ann. Comb., 15(2011), 355-380. Google Scholar
[21]	E. Teufl and S. Wagner, Determinant identities for Laplace matrices, Linear Algebra Appl., 432(2010), 441-457. Google Scholar
[22]	E. Teufl and S. Wagner, On the number of spanning trees on various lattices, J. Phys. A, 43(2010), 415001. Google Scholar
[23]	F.Y. Wu,The Potts model, Rev. Mod. Phys., 54(1982), 235-268. Google Scholar
[24]	B.Y. Wu and K.M. Chao, Spanning Trees and Optimization Problems, Chapman & Hall, FL, 2004. Google Scholar
[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. Google Scholar
[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. Google Scholar
[27]	Z.Z. Zhang, B. Wu and F. Comellas, The number of spanning trees in Apollonian networks, Discrete Appl. Math., 169(2014), 206-213. Google Scholar
[28]	J.Y. Zhang, W.G. Sun and G.H. Xu, Enumeration of spanning trees on Apollonian networks, J. Stat. Mech., 9(2013), P09015. Google Scholar