Tutte polynomial of pseudofractal scale-free web
arXiv:1207.6864 · doi:10.1007/s10955-015-1225-x
Abstract
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.
arXiv comment19pages,7figures. arXiv admin note: text overlap with arXiv:1006.5333
References in corpus (22)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Error and attack tolerance of complex networks
- Network robustness and fragility: Percolation on random graphs
- Cascade-based attacks on complex networks
- Breakdown of the Internet under intentional attack
- Pseudofractal Scale-free Web
- Enhancing network robustness for malicious attacks
- Spanning trees on the Sierpinski gasket
- Exact solution for mean first-passage time on a pseudofractal scale-free web
- Exact Potts Model Partition Functions on Ladder Graphs
- Chromatic Polynomials for Families of Strip Graphs and their Asymptotic Limits
- Enumeration of spanning trees in a pseudofractal scale-free web
- A general geometric growth model for pseudofractal scale-free web
- Exact Potts Model Partition Function on Strips of the Triangular Lattice
- Evolving small-world scale-free networks consist of cliques
- Exact Potts Model Partition Function for Strips of the Square Lattice
- Counting spanning trees in a small-world Farey graph
- Exact Potts Model Partition Functions on Strips of the Honeycomb Lattice
- Reliability Polynomials and their Asymptotic Limits for Families of Graphs
- The Tutte polynomial of the Sierpinski and Hanoi graphs
- Exact Potts/Tutte Polynomials for Polygon Chain Graphs