  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 gain recursive formulas for the Tutte polynomial of
pseudofractal scale-free web (PSW) which implies logarithmic complexity
algorithm is obtained to calculate the Tutte polynomial of PSW although it is
NP-hard for general graph. We also obtain the rigorous solution for the the
number of spanning trees of PSW by solving the recurrence relations derived
from Tutte polynomial, which give an alternative approach for explicitly
determining the number of spanning trees of PSW. Further more, we analysis the
all-terminal reliability of PSW and compare the results with that of Sierpinski
gasket which has the same number of nodes and edges with PSW. In contrast with
the well-known conclusion that scale-free networks are more robust against
removal of nodes than homogeneous networks (e.g., exponential networks and
regular networks). Our results show that Sierpinski gasket (which is a regular
network) are more robust against random edge failures than PSW (which is a
scale-free network). Whether it is true for any regular networks and scale-free
networks, is still a unresolved problem.
