Tutte polynomial of pseudofractal scale-free web.

*(English)*Zbl 1323.05070Summary: The Tutte polynomial of a graph is a 2-variable polynomial which is quite important in both Combinatorics and Statistical Physics. It contains various numerical invariants and polynomial invariants, such as the number of spanning trees, the number of spanning forests, the number of acyclic orientations, the reliability polynomial, chromatic polynomial and flow polynomial. In this paper, we study and obtain a recursive formula for the Tutte polynomial of pseudofractal scale-free web (PSFW), and thus a logarithmic complexity algorithm to calculate the Tutte polynomial of the PSFW is obtained, although it is NP-hard for general graph. By solving the recurrence relations derived from the Tutte polynomial, a rigorous solution for the number of spanning trees of the PSFW is obtained. Therefore, an alternative approach to determine explicitly the number of spanning trees of the PSFW is given. Furthermore, we analyze the all-terminal reliability of the PSFW and compare the results with those of the Sierpinski gasket which has the same number of nodes and edges as the PSFW. In contrast with the well-known conclusion that inhomogeneous networks (e.g., scale-free networks) are more robust than homogeneous networks (i.e., networks in which each node has approximately the same number of links) with respect to random deletion of nodes, the Sierpinski gasket (which is a homogeneous network), as our results show, is more robust than the PSFW (which is an inhomogeneous network) with respect to random edge failures.

##### MSC:

05C31 | Graph polynomials |

05C90 | Applications of graph theory |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

##### References:

[1] | Tutte, WT, A ring in graph theory, Proc. Camb. Philos. Soc., 43, 26-40, (1947) · Zbl 0031.41803 |

[2] | Tutte, WT, A contribution to the theory of chromatic polynomials, Can. J. Math., 6, 80-91, (1954) · Zbl 0055.17101 |

[3] | Tutte, WT, On dichromatic polynomials, J. Comb. Theory, 2, 301-320, (1967) · Zbl 0147.42902 |

[4] | Ellis-Monaghan, J., Merino, C.: Graph polynomials and their applications I: the Tutte polynomial. In: Dehmer, M. (ed.) Structural Analysis of Complex Networks. http://arxiv.org/abs/0803.3079v2 (in press) |

[5] | Chang, S-C; Chen, L-C; Yang, W-S, Spanning trees on the Sierpiński gasket, J. Stat. Phys., 126, 649-667, (2007) · Zbl 1110.82007 |

[6] | Zhang, ZZ; Wu, B; Lin, Y, Counting spanning trees in a small-world Farey graph, Phys. A, 391, 3342-3349, (2012) |

[7] | Chang, S-C; Chen, L-C, Number of connected spanning subgraphs on the Sierpiński gasket, Discrete Math. Theor. Comput. Sci., 11, 55-77, (2009) · Zbl 1196.05040 |

[8] | Chang, S-C; Chen, L-C, Spanning forests on the Sierpiński gasket, Discrete Math. Theor. Comput. Sci., 10, 55-76, (2008) · Zbl 1151.82316 |

[9] | Chang, S.-C.: Acyclic orientations on the Sierpiński gasket. Int. J. Mod. Phys. B 05 (2010) |

[10] | Chang, S-C; Shrock, R, Flow polynomials and their asymptotic limits for lattice strip graphs, J. Stat. Phys., 112, 815-879, (2003) · Zbl 1035.82011 |

[11] | Chang, S-C; Shrock, R, Reliability polynomials and their asymptotic limits for families of graphs, J. Stat. Phys., 112, 1019-1077, (2003) · Zbl 1118.82301 |

[12] | Rocek, M; Shrock, R; Tsai, SH, Chromatic polynomials for families of strip graphs and their asymptotic limits, Phys. A, 252, 505-546, (1998) |

[13] | Shrock, R; Xu, Y, Chromatic polynomials of planar triangulations, the Tutte upper bound, and chromatic zeros, J. Phys. A Math. Theor., 45, 0552122012, (2012) · Zbl 1241.05051 |

[14] | Welsh, DJA; Merino, C, The Potts model and the Tutte polynomial, J. Math. Phys., 41, 1127-1152, (2000) · Zbl 1045.82501 |

[15] | Shrock, R, Exact Potts-Tutte polynomials for polygon chain graphs, J. Phys. A Math. Theor., 44, 145002, (2011) · Zbl 1220.82028 |

[16] | Fortuin, CM, On the random-cluster model II. the percolation model, Physica, 58, 393-418, (1972) |

[17] | Oxley, J., Welsh, D.J.A.: The Tutte polynomial and percolation. In: Bondy, J.A., Murty, U.S.R. (eds.) Graph Theory and Related Topics (Proceeding of Conference, University of Waterloo, Waterloo, Ontario, 1977), pp. 329-339. Academic Press, New York, London (1979) · Zbl 0498.05018 |

[18] | Jaeger, F; Vertigan, DL; Welsh, DJA, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Camb. Philos. Soc., 108, 35-53, (1990) · Zbl 0747.57006 |

[19] | Oxley, J; Welsh, D, Chromatic, flow and reliability polynomials: the complexity of their coefficients, Comb. Probab. Comput., 11, 403-426, (2002) · Zbl 1001.05034 |

[20] | Donno, A; Iacono, D, The Tutte polynomial of the sierpinski and Hanoi graphs, Adv. Geom., 13, 663-694, (2013) · Zbl 1275.05030 |

[21] | Chang, S-C; Shrock, R, Exact Potts model partition functions for strips of the honeycomb lattice, Phys. A, 296, 183-233, (2001) · Zbl 0978.82020 |

[22] | Chang, S-C; Shrock, R, Exact Potts model partition function on strips of the triangular lattice, Phys. A, 286, 189-238, (2000) · Zbl 1052.82513 |

[23] | Salas, J; Chang, S-C; Shrock, R, Exact Potts model partition function for strips of the square lattice, J. Stat. Phys., 107, 1207-1253, (2002) · Zbl 1015.82006 |

[24] | Shrock, R, Exact Potts model partition functions on ladder graphs, Physica A, 283, 388-446, (2000) |

[25] | Barabási, A-L; Albert, R, Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223 |

[26] | Watts, DJ; Strogatz, H, Collective dynamics of ’small-world’ networks, Nature (London), 393, 440-442, (1998) · Zbl 1368.05139 |

[27] | Dorogovtsev, SN; Goltsev, AV; Mendes, JFF, Pseudofractal scale-free web, Phys. Rev. E, 65, 066122, (2002) |

[28] | Zhang, ZZ; Rong, LL; Zhou, SG, A general geometric growth model for pseudofractal scale-free web, Phys. A, 377, 329-339, (2007) |

[29] | Zhang, ZZ; Zhou, SG; Chen, LC, Evolving pseudofractal networks, Eur. Phys. J. B., 58, 337-344, (2007) |

[30] | Zhang, ZZ; Liu, HX; Wu, B; Zhou, SG, Enumeration of spanning trees in a pseudofractal scale-free web, Europhys. Lett., 90, 68002, (2010) |

[31] | Zhang, ZZ; Qi, Y; Zhou, SG; Xie, WL; Guan, JH, Exact solution for Mean first-passage time on a pseudofractal scale-free web, Phys. Rev. E, 79, 021127, (2009) |

[32] | Albert, R; Jeong, H; Barabási, A-L, Error and attack tolerance of complex networks, Nature, 406, 378-482, (2000) |

[33] | Albert, R; Barabási, A-L, Statistical mechanics of complex networks, Rev. Mod. Phys., 74, 47-97, (2002) · Zbl 1205.82086 |

[34] | Motter, AE; Lai, YC, Cascade-based attacks on complex networks, Phys. Rev. E, 66, 065102, (2002) |

[35] | Bollt, EM; ben-Avraham, D, What is special about diffusion in scale-free networks, New J. Phys., 7, 26, (2005) |

[36] | Chang, S-C; Chen, L-C; Yang, W-S, Spanning trees on the Sierpiński gasket, J. Stat. Phys., 126, 649-667, (2007) · Zbl 1110.82007 |

[37] | Mandelbrot, B.: The Fractal Geometry of Nature, pp. 193-195. Freeman, Francisco (1982) · Zbl 0504.28001 |

[38] | Hilfer, R; Blumen, A, Renormalisation on sierpinski-type fractals, J. Phys. A Math. Gen., 17, l537-l545, (1984) |

[39] | Callaway, DS; Newman, MEJ; Strogatz, SH; Watts, DJ, Network robustness and fragility: percolation on random graphs, Phys. Rev. Lett., 85, 5468-5471, (2000) |

[40] | Cohen, R; Erez, K; ben-Avraham, D; Havlin, S, Breakdown of the Internet under intentional attack, Phys. Rev. Lett., 86, 3682, (2001) |

[41] | Zeng, A; Liu, WP, Enhancing network robustness against malicious attacks, Phys. Rev. E, 85, 066130, (2012) |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.