The Tutte polynomial of a graph, or equivalently the q-state Potts model partition function, is a two-variable polynomial graph invariant of considerable importance in both combinatorics and statistical physics. The computation of this invariant for a graph is NP-hard in general. The aim ...
In this paper we recursively describe the Tutte polynomial of an infinite family of outerplanar, small-world and self-similar graphs. In particular, we study the Abelian Sandpile Model on these graphs and obtain the generating function of the recurrent configurations. Furthe ...
In this paper, we find recursive formula for the Tutte polynomial of a family of smallworld Farey graph, which is modular and has an exponential degree hierarchy. As the applications of the recursive formula, the exact expressions for the chromatic polynomial and the reliability polynomial ...
Tittmann, Averbouch and Makowsky introduced the subgraph component polynomial Q(G; x, y) of a graph G, which counts the number of connected components in vertex induced subgraphs. This polynomial encodes a large amount of combinatorial information about the underlying grap ...