Tutte Polynomial of Pseudofractal Scale-Free Web

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 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, the 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.