一类连通图的Tutte多项式

The Tutte Polinomials of a Kind of Connected Graphs

摘要: 近年来，随着拓扑学家对纽结理论的深入研究，空间图理论逐渐成为学者们的研究热点。Tutte多项式在空间图理论中具有重要地位，本文利用缩边与减边的性质，借助二元的数学归纳法计算了一类连通图的Tutte多项式，最终得出这类连通图的Tutte多项式。

Abstract: In recent years, with the in-depth research of mathematicians in the field of topology, spatial graph theory gradually becomes a hot topic for scholars. The Tutte polynomials occupy a central place in spatial graph theory. In this paper, we calculate the Tutte polynomials of a kind of connected graphs by quality of edge and Mathematical induction of two variables, lastly, we get the Tutte polynomials of this kind of connected graphs.

1. 引言

Tutte多项式是空间图多项式不变量的一个重要代表，Tutte多项式包含了图的大量信息 [1] ，由Tutte多项式可以得到图的生成森林数、连通子图数、无圈定向数等 [2] ，且由Tutte多项式可以得到链多项式、Flow多项式等图的多项式不变量 [3] 。近年来，学者们提出了许多关于Tutte多项式的研究课题，Doslic直接利用Tutte多项式删边与减边的性质计算出书图的具体表达式 [4] ，Brennan利用生成函数的方法计算出扇图的Tutte多项式 [5] ，廖云华利用生成子图展开定义得到了几类网格图的Tutte多项式，并且通过计算出其某些特殊点的值来得到图的重要参数 [6] 。Kung从多角度对Tutte多项式进行阐述 [7] 。

本文计算一类图的Tutte多项式，共分为两部分，第一部分介绍了相关的基础知识，在第二部分中，首先计算得到图 $(4,m,n)$ 的Tutte多项式。在此基础上，计算得到图 $(A,m,n)$ 的Tutte多项式。

2. 预备知识

2.1. 图

定义1.1将有序三元组 $(V(G),E(G),\phi (G))$ 称作图，记为G。将 $V(G)$ 记为图G的顶点集， $E(G)$ 记为图G的边集，并且 $E(G)\cap V(G)=\varnothing$ ， $\phi (G)$ 将G的每条边对应G的定点对(顶点可以是同一个)。若边e与两个顶点 $u,v$ 满足 $\phi (e)=uv$ ，则称顶点 $u,v$ 是用边e连接的，e的两个端点是顶点 $u,v$ 。

注释1.1若在图G中删除边e后，图G的分支数增加，则称边e为图G的割边。

注释1.2若边e的两个端点是相同的顶点，则e为环边。

注释1.3若连接同一对顶点的边数大于1，则这样的边称为多重边。

2.2. 连通图

定义1.4若从顶点V₁到顶点V₂有路径，则称顶点V₁与顶点V₂是连通的。如果图中任意一对顶点都是连通的，则称此图为连通图。即图中任意两顶点间至少有一条路径。如图1左图为连通图，右图为非连通图。(注：本文涉及的图均为连通平面图。)

Figure 1. Connected graph and unconnected graph

图1. 连通图与非连通图

2.3. Tutte多项式

性质1：当图G的边集是空集时， $T_G(x,y)=1$ ；

性质2：当e是环边时， $T_G(x,y)=yT(G-e;x,y)$ ；

性质3：当e是割边时， $T_G(x,y)=xT(G/e;x,y)$ ；

性质4：当e不是环边也不是割边时， $T_G(x,y)=T(G/e;x,y)+T(G-e;x,y)$ 。

3. $(A,m,n)$ 图的Tutte多项式

3.1. $(4,m,n)$ 图的Tutte多项式的计算

定义2.1在四边形的基础上，任意选择一组对边，分别增加m条边和n条边，得到的图称为 $(4,m,n)$ 图(如图2)。

Figure 2. Graph $(4,m,n)$

图2. 图 $(4,m,n)$

定理2.1图G $(4,m,n)$ 的Tutte多项式为：

$T_{(4,m,n)}(x,y)=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i})+(x+y){\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}$

证明：当 $m=1$ ，

$n=1$ 时， $T$ ( ) $=T$ ( ) $+T$ ( )

$=T$ ( ) $+T$ ( ) $+yT$ ( )

$=x^3+T$ ( ) $+yT$ ( ) $+y[T$ ( )

$+yT$ ( ) $]$

$=x^3+(x^2+x+y)(1+y)+y(x^2+x+y)+y^2(x+y)$

$=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{1}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{1}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{1}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{1}{\sum }}{y}^i}$

假设 $n=k$ 时， $T(1,k)=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{1}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{k}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{1}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{k}{\sum }}{y}^i}$ ，

下证 $n=k+1$ 成立， $T(1,k+1)=T$ ( ) $=T$ ( ) $+T$ ( )

$\begin{array}{l}=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{1}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{k}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{1}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{k}{\sum }}{y}^i}\\ +y^{k+1}[(x^2+x+y)+y(x+y)]\end{array}$

$=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{1}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{k+1}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{1}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{k+1}{\sum }}{y}^i}$

则 $T(1,n)=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{1}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{1}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}$ 成立。

与 $T(1,n)$ 同理，利用Tutte多项式减边缩边性质可以证得：

$T(m,1)=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{1}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{1}{\sum }}{y}^i}$ .

设 $T(m+1,n)=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{m+1}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{m+1}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}$ ；

$T(m,n+1)=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{n+1}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n+1}{\sum }}{y}^i}$ ，

下证 $T(n+1,m+1)$ 成立，

$T(n+1,m+1)=T$ ( ) $=T$ ( ) $+T$ ( )

$=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{m+1}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{m+1}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}+y^{n+1}T$ ( )

其中， $T$ ( ) $=T$ ( ) + $(y+y^2+\cdots +y^{m+1})T$ ( )

$=x^2+x+y+(x+y){\displaystyle \underset{i=1}{\overset{m+1}{\sum }}{y}^i}$

则

$\begin{array}{c}T(n+1,m+1)=x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{m+1}{\sum }}{y}^i+}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i)}+(x+y){\displaystyle \underset{i=1}{\overset{m+1}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}+y^{n+1}[x^2+x+y+(x+y){\displaystyle \underset{i=1}{\overset{m+1}{\sum }}{y}^i}]\\ =x^3+(x^2+x+y)({\displaystyle \underset{i=0}{\overset{m+1}{\sum }}{y}^i}+{\displaystyle \underset{i=1}{\overset{n+1}{\sum }}{y}^i})+(x+y){\displaystyle \underset{i=1}{\overset{m+1}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n+1}{\sum }}{y}^i}\end{array}$

定理2.1得证。

3.2. $(A,m,n)$ 图的Tutte多项式的计算

定义5.1在A边形( $A\ge 5$ )的基础上，任选两邻边，分别为其增加m条边和n条边，得到的图称为 $(A,m,n)$ 图(如图3)。

Figure 3. Graph $(A,m,n)$

图3. 图 $(A,m,n)$

定理5.1 $(A,m,n)$ 图的Tutte多项式为：

$T_{(A,m,n)}(x,y)=x^{A-1}+T_{C_{A-1}}({\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i})+T_{C_{A-2}}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}$

证明：当 $n=5$ 时，与 $(4,m,n)$ 图的Tutte多项式一样，借助二变量的数学归纳法即可证明成立。

设 $A=k$ 成立，即 $T_{(k,m,n)}(x,y)=x^{k-1}+T_{C_{k-1}}({\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i})+T_{C_{k-2}}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}$ ，

下证 $A=k+1$ 成立。

$T_{(k+1,m,n)}=T$ ( ) $=T$ ( ) $+T_{(k,m,n)}$

$=x^{k-2}T$ ( ) $T$ ( ) $+T_{(k,m,n)}$

其中， $T$ ( ) $=x^{k-2}[T$ ( ) $+T$ ( )

$+T$ ( ) $+T$ ( )

$=x^{k-2}(x+y+y^2+\cdots +y^n)$

则

$\begin{array}{c}{T}_{(k+1,m,n)}=x^{k-2}(x+y+y^2+\cdots +y^n)(x+y+y^2+\cdots +y^m)+T_{(k,m,n)}\\ =x^{k-2}(x+y+y^2+\cdots y^n)(x+y+y^2+\cdots +y^m)+x^{k-1}+T_{C_{k-1}}({\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i})+T_{C_{k-2}}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}\\ =x^{k-2}(x+y+y^2+\cdots +y^n)(x+y+y^2+\cdots +y^m)\\ +x^{k-1}+(x+x^2+\cdots +x^{k-2}+y)({\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i})+(x+x^2+\cdots +x^{k-3}+y){\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}\\ =x^{k-2}[(x^2+x(y+y^2+\cdots +y^m)+x(y+y^2+\cdots +y^n)+(y+y^2+\cdots +y^m)(y+y^2+\cdots +y^n)]\\ +x^{k-1}+(x+\cdots +x^{k-2}+y)({\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i})+(x+\cdots +x^{k-3}+y){\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}\end{array}$

$\begin{array}{c}=x^k+x^{k-1}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}+x^{k-1}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}+x^{k-2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}+x^{k-1}\\ +(x+\cdots +x^{k-2}+y){\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+(x+\cdots +x^{k-2}+y){\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}+(x+\cdots +x^{k-3}+y){\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}\\ =x^k+(x+\cdots +x^{k-1}+y){\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+(x+\cdots +x^{k-1}+y){\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}+(x+\cdots +x^{k-2}+y){\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}\\ =x^k+T_{C_k}{\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+T_{C_k}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}+T_{C_{k-1}}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}\\ =x^k+T_{C_k}({\displaystyle \underset{i=0}{\overset{m}{\sum }}{y}^i}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i})+T_{C_{k-1}}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}^i}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{y}^i}\end{array}$

定理5.1得证。

4. 结论

本文主要研究了一类 $(A,m,n)$ ( $A\ge 4$ )图的Tutte多项式，目前学者们只得到轮图、扇图与花图Tutte多项式的具体表达，未来会得到更多图的Tutte多项式，也可以进一步分析得到图的很多信息与参数。