  Spanning trees are an important quantity characterizing the reliability of a
network, however, explicitly determining the number of spanning trees in
networks is a theoretical challenge. In this paper, we study the number of
spanning trees in a small-world scale-free network and obtain the exact
expressions. We find that the entropy of spanning trees in the studied network
is less than 1, which is in sharp contrast to previous result for the regular
lattice with the same average degree, the entropy of which is higher than 1.
Thus, the number of spanning trees in the scale-free network is much less than
that of the corresponding regular lattice. We present that this difference lies
in disparate structure of the two networks. Since scale-free networks are more
robust than regular networks under random attack, our result can lead to the
counterintuitive conclusion that a network with more spanning trees may be
relatively unreliable.
