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

Yunhua Liao, M.A. Aziz-Alaoui, Junchan Zhao and Yaoping Hou

Applied Mathematics and Computation, 2019, vol. 363, issue C, -

Abstract: 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.

Keywords: Tutte polynomial; Graph operation; Tensor product; Spanning tree; Network model (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319306332
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:363:y:2019:i:c:37

DOI: 10.1016/j.amc.2019.124641

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().