×

Tutte polynomial of tensor product graph and its applications. (Chinese. English summary) Zbl 07801749

Summary: Let \(G\) be a connected graph with \(m\) edges. \(\mathcal{H}=\{H_1,H_2,\dots, H_m\}\) is a set of disjoint graphs. \(H_i\) is a connected graph with two distinct vertices \(u_i\) and \(v_i\), \(i=1,2,\dots,m\). The tensor product of \(G\) and \(\mathcal{H}\), denoted by \(G[\mathcal{H}]\), is the graph obtained from \(G\) by replacing edge \(e_i\) of \(G\) with \(H_i\) for \(1\leq i\leq m\). In this paper, only using classical graph theory, we obtain a formula for the Tutte polynomial of the tensor product \(G[\mathcal{H}]\). Firstly, we divide the set of spanning subgraphs of \(H_i\) into two disjoint subsets according to whether the two distinct vertices \(u_i\) and \(v_i\) are contained in the same connected component or not. In this way, we split the Tutte polynomial of \(H\) into two parts, \(T_1(H;x,y)\) and \(T_2(H;x,y)\). By using the connection between the subgraphs of \(H\) and that of \(H/uv\), we derive expressions for \(T_1(H;x,y)\) and \(T_2(H;x,y)\) in terms of \(T(H;x,y)\) and \(T(H/uv;x,y)\). Secondly, we partition the set of spanning subgraphs of \(G[\mathcal{H}]\) into \(2^{|E(G)|}\) disjoint subsets according to the construction method of \(G[\mathcal{H}]\). Applying an indirect way, we obtain a formula for the contribution to \(T(G[\mathcal{H}];x,y)\) of each subset. Thirdly, we sum over the contribution of each subset and obtain an expression for \(T(G[\mathcal{H}];x,y)\). As applications, we show that the Tutte polynomials of several operation graphs can be deduced from our result directly. Finally, we discuss why our method can work well and in which situation our technique can be applied to study graph polynomials.

MSC:

05C31 Graph polynomials
05C76 Graph operations (line graphs, products, etc.)
05C30 Enumeration in graph theory
05C05 Trees
05C90 Applications of graph theory

References:

[1] Tutte W T. A contribution to the theory of chromatic polynomials. Canadian Journal of Mathematics, 1954, 6: 80-91 · Zbl 0055.17101
[2] Beaudin L, Ellis-Monaghan J A, Pangborn G, Shrock R. A little statistical mechanics for the graph theorist. Discrete Mathematics, 2010, 310: 2037-2053 · Zbl 1223.05125
[3] Mier A D, Noy M. On graphs determined by their Tutte polynomials. Graphs and Combinatorics, 2004, 20: 105-119 · Zbl 1053.05057
[4] ÏJ_, o©•, 4¸. Fã ‚ã Tutte •˜5. &²nóOEAEAE (g,‰AE ‡), 2012, 37(4): 92-96 (Hao R X. Li W Q, Liu F. Tutte-uniqueness of line graphs of ladders. Journal of Kunming University of Science and Technology, 2012, 37(4): 92-96)
[5] u, û. ü:ëã Tutte õ’ª9A^. A^êAEAE , 2016, 39(3): 392-402
[6] Liao Y H, Xie X L. Tutte polynomial of two point join graph and its application. Acta Mathematicae Applicatae Sinica, 2016, 39(3): 392-402) · Zbl 1363.05120
[7] Chen H L, Deng H Y. Tutte polynomial of scale-free networks. Journal of Statistical Physics, 2016, 163: 714-732 · Zbl 1342.82022
[8] Liao Y H, Aziz-Alaoui M A, Zhao J C, Hou Y P, The behavior of Tutte polynomials of graphs under five graph operations and its applications. Applied Mathematics and Computation, 2019, 363: 124641 · Zbl 1433.05163
[9] Awan J, Bernardi O. Tutte polynomials for directed graphs. Journal of Combinatorial Theory, Series B, 2020, 140: 192-247 · Zbl 1430.05057
[10] Kahl N. Extremal graphs for the Tutte polynomial. Journal of Combinatorial Theory, Series B, 2022, 152: 121-152 · Zbl 1478.05081
[11] Welsh D, Merino C. The Potts model and the Tutte polynomial. Journal of Mathematical Physics, 2000, 41: 1127-1152 · Zbl 1045.82501
[12] Ellis-Monaghan J A, Merino C. Graph polynomials and their applications I: The Tutte polynomial. In: Dehmer M (ed.), Structural Analysis of Complex Networks, Birkhauser, Boston, 2011, 219-255 · Zbl 1221.05002
[13] Jaeger F, Vertigan D L, Welsh D J A. On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society, 1990, 108: 35-53 · Zbl 0747.57006
[14] oO¬, ñ2¸. ˜a
[15] Li A M, Jiang G F. Tutte polynomials of a class of carbon nanotube-like graph. Journal of Beijing University of Chemical Technology (Natural Science), 2011, 38: 130-135)
[16] Ren H Z, Xu D Q, Yang W L. The Tutte polynomials of catacondensed benzenoid systems. Journal of Mathematical Chemistry, 2021, 59: 529-541 · Zbl 1466.92282
[17] Ma T L, Jin X A, Zhang F J. Tutte polynomials of fan-like graphs with applications in benzenoid systems. Applied Mathematics and Computation, 2021, 411: 126496 · Zbl 1510.05128
[18] Gong H L, Jin X A. Potts model partition functions for two families of fractal lattices. Physica A, 2014, 414: 143-153 · Zbl 1395.82046
[19] Gong H L, Jin X A. A general method for computing Tutte polynomials of self-similar graphs. Physica A, 2017, 483: 117-129 · Zbl 1499.82007
[20] Chen H L. The Tutte polynomial of a class of compound graphs and its applications. Discrete Mathematics, Algorithms and Applications, 2023, 15: 2250058 · Zbl 1516.05105
[21] Huggett S, Moffatt I. Expansions for the Bollobás-Riordan polynomial of separable ribbon graphs. Annals of Combinatorics, 2011, 15: 675-706 · Zbl 1234.05125
[22] Ellis-Monaghan J, Moffatt I. Evaluations of topological Tutte polynomials. Combinatorics, Probability and Computing, 2015, 24: 556-583 · Zbl 1371.05134
[23] Yan W G, Yeh Y N. On the number of matchings of graphs formed by a graph operation. Science in China: Series A Mathematics, 2006, 49, 1383-1391 · Zbl 1110.05085
[24] Guo Z L, Li S C, Liu X, Mei X L. Expected hitting times for random walks on the diamond hierarchical graphs involving some classical parameters. Linear and Multilinear Algebra, 2019, 69(10): 1841-1857 · Zbl 1472.05135
[25] Dorogovtsev S N, Goltsev A V, Mendes J F F. Pseudofractal scale-free web. Physical Review E, 2002, 65, 066122
[26] Rozenfeld H D, ben-Avraham D. Percolation in hierarchical scale-free nets. Physical Review E, 2007, 75: 061102
[27] Traldi L. A dichromatic polynomial for weighted graphs and link polynomials. Proceedings of the American Mathematical Society, 1989, 106: 279-286 · Zbl 0713.57003
[28] Jin X A, Zhang F J. The Homfly and dichromatic polynomial. Proceedings of the American Mathe-matical Society, 2012, 140: 1459-1472 · Zbl 1241.57004
[29] West D B. Introduction to Graph Theory. Beijing: China Machine Press, 2004
[30] Woodall D R. Tutte polynomial expansion for 2-separable graphs. Discrete Mathematics, 2002, 247: 201-213 · Zbl 0996.05054
[31] Gong H L, Li S L. The number of spanning trees of a family of 2-separable weighted graphs. Discrete Applied Mathematics, 2017, 229: 154-160 · Zbl 1367.05095
[32] Li T Y, Yan W G. Enumeration of spanning trees of 2-separable networks. Physica A, 2019, 536: 120877 · Zbl 07571462
[33] Hayat S, Imran M. Computation of topological indices of certain networks. Applied Mathematics and Computation, 2014, 240: 213-228 · Zbl 1334.05160
[34] Shoaib M S, Pan X F, Xu S A. Computation of resistance distance and Kirchhoff index of the two classes of silicate networks. Applied Mathematics and Computation, 2020, 381: 125283 · Zbl 1462.05127
[35] Sun B B, Yao J L, Xi L F. Eigentime identities of fractal sailboat networks. Physica A, 2019, 520: 338-349 · Zbl 1515.90039
[36] Xi L F, Ye Q Q. Eigentime identities of potting networks. Physica A, 2019, 526: 120934 · Zbl 07566421
[37] Fan J Q, Zhu J L, Tian L, Wang Q. Resistance distance in potting networks. Physica A, 2020, 540: 123053 · Zbl 07457943
[38] Iglói F, Turban L. Disordered Potts model on the diamond hierarchical lattice: Numerically exact treatment in the large-q limit. Physical Review B, 2009, 80: 134201
[39] Li D Q, Hou Y P. The normalized Laplacian spectrum of quadrilateral graphs and its applications. Applied Mathematics and Computation, 2017, 297: 180-188 · Zbl 1411.05171
[40] Negami S. Polynomial invariants of graphs. Transactions of The American Mathematical Society, 1987, 299: 601-622 · Zbl 0674.05062
[41] Xi L F, Ye Q Q, Yao J L, Sun B B. Eigentime identities of flower networks with multiple branches. Physica A, 2019, 526, 120857 · Zbl 07566394
[42] Azarija J. Tutte polynomials and a stronger version of the Akiyama-Harary problem. Graphs and Combinatorics, 2015, 31: 1155-1161 · Zbl 1326.05066
[43] Gong H L, Metsidik M. Constructions of pairs of Tutte-equivalent graphs. Ars combinatorica, 2017, 135: 223-234 · Zbl 1463.05292
[44] Kauffman L H. A Tutte polynomial for signed graph. Discrete Applied Mathematics, 1989, 25: 105-127 · Zbl 0698.05026
[45] Jin X A, Zhang F J, Dong F M, Tay E G. Zeros of the Jones polynomial are dense in the complex plane. Electronic Journal of Combinatorics, 2010, 17: R94 · Zbl 1230.05110
[46] Jin X A, Zhang F J. The Jones polynomial for polyhedral links. MATCH Communications in Math-ematical and in Computer Chemistry, 2011, 65: 501-520 · Zbl 1299.05176
[47] Jin X A, Zhang F J. The architecture and the Jones polynomial of polyhedral links. Journal of Mathematical Chemistry, 2011, 49: 2063-2088 · Zbl 1314.92117
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.