张量积图的Tutte多项式及其应用

来源：应用数学学报杂志2023年第4期北京时间：

作者：杨刚, 廖云华

单位：1 湖南工商大学理学院, 长沙 410205;<br>2 统计学习与智能计算湖南省重点实验室, 长沙 410205

摘要：图$G$为具有$m$条边的连通图,$E (G)=\{e_1,e_2,\cdots,e_m\}$,$\mathcal{H}=\{H_1,H_2,\cdots,H_m\}$为由$m$个连通图构成的集合.图$G[\mathcal{H}]$为$G$与$\mathcal{H}$的张量积图,即对每个$i$$(1\leq i\leq m)$,$e_i$被$H_i$替代而得到的图.张量积这一图运算包含了多个边替代图运算,例如细分、三角化、钻石化等图运算.本文中,我们给出了$G[\mathcal{H}]$的Tutte多项式的显式表达式,进而得到了细分图、三角化图、钻石化图等运算图的Tutte多项式和生成树数目.

关键词：Tutte多项式,张量积,图运算,生成树数目