×

The behavior of Tutte polynomials of graphs under five graph operations and its applications. (English) Zbl 1433.05163

Summary: 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 \(R_2(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.

MSC:

05C31 Graph polynomials
05C76 Graph operations (line graphs, products, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Tutte, W. T., A contribution to the theory of chromatic polynomials, Can. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
[2] Ellis-Monaghan, J. A.; Merino, C., Graph polynomials and their applications I: the Tutte polynomial, (Dehmer, M., Structural Analysis of Complex Networks (2011), Birkhäuser), 219-255 · Zbl 1221.05002
[3] Welsh, D. J.A.; Merino, C., The Potts model and the Tutte polynomial, J. Math. Phys., 41, 1127-1152 (2000) · Zbl 1045.82501
[4] Mier, A. D.; Noy, M., On graphs determined by their Tutte polynomials, Gr. Comb., 20, 105-119 (2004) · Zbl 1053.05057
[5] Huang, J.; Li, S. C., On the normalized Laplacian, degree-kirchhoff index and spanning trees of graphs, Bull. Aust. Math. Soc., 91, 353-367 (2015) · Zbl 1326.05082
[6] Xie, P. C.; Zhang, Z. Z.; Comellas, F., On the spectrum of normalized Laplacian of iterated triangulations of graphs, Appl. Math. Comput., 273, 1123-1129 (2016) · Zbl 1410.05143
[7] Xie, P. C.; Zhang, Z. Z.; Comellas, F., The normalized Laplacian spectrum of subdivisions of a graph, Appl. Math. Comput., 286, 250-256 (2016) · Zbl 1410.05144
[8] Li, D. Q.; Hou, Y. P., The normalized Laplacian spectrum of quadrilateral graphs and its applications, Appl. Math. Comput., 297, 180-188 (2017) · Zbl 1411.05171
[9] Zhang, Z. Z.; Liu, H. X.; Wu, B.; Zhou, S. G., Enumeration of spanning trees in a pseudofractal scale-free web, EPL, 90, 68002 (2010)
[10] Lin, Y.; Wu, B.; Zhang, Z. Z.; Chen, G. R., Counting spanning trees in self-similar networks by evaluating determinants, J. Math. Phys., 52, 113303 (2011) · Zbl 1272.05187
[11] Seymour, P. D., Decomposition of regular matroids, J. Comb. Theory Ser. B, 28, 305-359 (1980) · Zbl 0443.05027
[12] Brylawski, T. H., The tutte polynomial i: general theory, (Barlotti, A., Matroid Theory and Its Applications (1982)), 125-275 · Zbl 1302.05023
[13] Woodall, D. R., Tutte polynomial expansions for 2-separable graphs, Discrete Math., 247, 201-213 (2002) · Zbl 0996.05054
[14] Huggett, S.; Moffatt, I., Expansions for the Bollobas-Riordan polynomial of separable ribbon graphs, Ann. Comb., 15, 675-706 (2011) · Zbl 1234.05125
[15] Ellis-Monaghan, J.; Moffatt, I., Evaluations of topological Tutte polynomials, Comb. Prob. Comput., 24, 556-583 (2015) · Zbl 1371.05134
[16] Goodall, A. J.; Merino, C.; Mier, A. D.; Noy, M., On the evaluation of the Tutte polynomial at the points \((1, - 1)\) and \((2, - 1)\), Ann. Comb., 17, 311-332 (2013) · Zbl 1270.05060
[17] Read, R. C., An introduction to chromatic polynomials, J. Comb. Theory, 4, 52-71 (1968) · Zbl 0173.26203
[18] Sokal, A. D., Chromatic roots are dense in the whole complex plane, Comb. Prob. Comput., 13, 221-261 (2004) · Zbl 1100.05040
[19] Beaudin, L.; Ellis-Monaghan, J.; Pangborn, G.; Shrock, R., A little statistical mechanics for the graph theorist, Discrete Math., 310, 2037-2053 (2010) · Zbl 1223.05125
[20] Silva, L. D.; Curado, E. M.F.; Coutinho, S.; Morgado, W. A.M., Criticality and multifractality of the Potts ferromagnetic model on fractal lattices, Phys. Rev. B, 53, 6345-6354 (1996)
[21] Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F.F., Pseudofractal scale-free web, Phys. Rev. E, 65, 066122 (2002)
[22] Zhang, Z. Z.; Zhou, S. G.; Chen, L. C., Evolving pseudofractal networks, Eur. Phys. J. B, 58, 337-344 (2007)
[23] Zhang, Z. Z.; Qi, Y.; Zhou, S. G.; Xie, W. L.; Guan, J. H., Exact solution for mean first-passage time on a pseudofractal scale-free web, Phys. Rev. E, 79, 021127 (2009)
[24] Peng, J. H.; Xiong, J.; Xu, G. A., Tutte polynomial of pseudofractal scale-free web, J. Stat. Phys., 159, 1196-1215 (2015) · Zbl 1323.05070
[25] Chen, H. L.; Deng, H. Y., Tutte polynomial of scale-free networks, J. Stat. Phys., 163, 714-732 (2016) · Zbl 1342.82022
[26] Liao, Y. H.; Hou, Y. P.; Shen, X. L., Tutte polynomial of a small-world Farey graph, EPL, 104, 38001 (2013)
[27] Gong, H. L.; Jin, X. A., A general method for computing Tutte polynomials of self-similar graphs, Phys. A, 483, 117-129 (2017) · Zbl 1499.82007
[28] Bollobás, B.; Riordan, O., A polynomial invariant of graphs on orientable surfaces, Math. Ann., 323, 81-96 (2002) · Zbl 1004.05021
[29] Trinks, M., The covered components polynomial: a new representation of the edge elimination polynomial, Electron. J. Comb., 19, P50 (2012) · Zbl 1243.05114
[30] Gutman, I.; Harary, F., Generalizations of the matching polynomial, Util. Math., 24, 97-106 (1983) · Zbl 0527.05055
[31] Farrell, F. J., An introduction to matching polynomials, J. Comb. Theory Ser. B, 27, 75-86 (1979) · Zbl 0335.05131
[32] Tittmann, P.; Averbouch, I.; Makowsky, J. A., The enumeration of vertex induced subgraphs with respect to the number of components, Eur. J. Comb., 32, 954-974 (2011) · Zbl 1229.05124
[33] Barabási, A. L.; Oltvai, Z. N., Network biology: understanding the cell’s functional organization, Nat. Rev. Genet., 5, 101-113 (2004)
[34] Rozenfeld, H.; Havlin, S.; ben Avraham, D., Fractal and transfractal recursive scale-free networks, New J. Phys., 9, 175 (2007)
[35] Ma, F.; Su, J.; Hao, Y. X.; Yao, B.; Yan, G. H., A class of vertex-edge-growth small-world network models having scale-free, self-similar and hierarchical characters, Phys. A, 492, 1194-1205 (2018) · Zbl 1514.91149
[36] Shen-Orr, S. S.; Milo, R.; Mangan, S.; Alon, U., Network motifs in the transcriptional regulation network of escherichia coli, Nat. Genet., 31, 64-68 (2002)
[37] Milo, R.; Shen-Orr, S.; Itzkovitz, S.; Kashtan, N.; Chklovskii, D.; Alon, U., Network motifs: simple building blocks of complex networks, Science, 298, 824-827 (2002)
[38] Voy, B. H.; Scharff, J. A.; Perkins, A. D.; Saxton, A. M.; Borate, B.; Chesler, E. J.; Branstetter, L. K.; Langston, M. A., Extracting gene networks for low-dose radiation using graph theoretical algorithms, PLoS Comput. Biol., 2, e89 (2006)
[39] Mehatari, R.; Banerjee, A., Effect on normalized graph Laplacian spectrum by motif attachment and duplication, Appl. Math. Comput., 261, 382-387 (2015) · Zbl 1410.05136
[40] Jackson, B.; Sokal, A. D., Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids, J. Comb. Theory Ser. B, 99, 869-903 (2009) · Zbl 1221.05144
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.