棱柱和Mobius梯的Tutte多项式

Tutte polynomials of prisms and Mobius ladders

棱柱是圈C_(n)和路P_(2)的笛卡尔积,也可以看作两端连接的梯图.Mobius梯的结构与棱柱相似,可看作扭曲后两端连接的梯图,并且自然地嵌入Mobius带.图的Tutte多项式是一个双变量多项式图不变量,通过对变量赋值或变换可以得到生成树数目、连通生成子图数目、色多项式和可靠多项式等许多图不变量.本文运用Tutte多项式的删除-收缩运算,获得了棱柱和Mobius梯的Tutte多项式.

A prism is a cartesian product of the cycle and the path can also be seen as a ladder graph connected at both ends.The structure of a Mobius ladder is similar to that of a prism,and can be seen as a twisted ladder graph connected at both ends,naturally embedded with straps.The Tutte polynomial of a graph is a bivariate polynomial graph invariant.By assigning or transforming variables,many graph invariants can be obtained,such as the number of spanning trees,the number of connected spanning subgraphs,chromatic polynomials,and reliability polynomials.This article uses the deletion-contraction operation of the Tutte polynomial to obtain the Tutte polynomials for prisms and Mobius ladders.