The behavior of Tutte polynomials of graphs under five graph operations and its applications

摘要

The Tutte polynomial of a graph has many important applications in combinatorics, physics, and biology. Graph operations, such as triangulation and subdivision, have been widely used in building complex network models. In this paper, we show how the Tutte polynomial changes with five graph operations. Firstly, we study the connections between graph G and its operation graphs: the triangulation graph R(G), the diamond graph Z(G), the quadrilateral graph Q(G), the 2-triangulation graph R2(G), and the Wheatstone bridge graph W(G), in the respect of spanning subgraphs. Secondly, using these relations, we investigate the structure of the set of spanning subgraphs of each operation graph, and find that it is constituted by 2|E(G)| disjoint subsets. Then, we derive the contribution of each subset by an indirect method. Finally, we gain the Tutte polynomials of these five operation graphs. Moreover, we consider the Tutte polynomials of the pseudofractal scale-free network and a classic diamond hierarchical lattice as an application. Our technique can be applied to study other graph polynomials.