一類特殊連圖的Tutte多項式

（遼寧師范大學 數學學院，遼寧 大連 116029）

1 引言及預備知識

圖論中有許多值得研究的問題，其中關于圖的等價分類問題就是圖理論中的重要問題之一.圖的不變量[1-7]是研究圖等價分類的重要方法.圖多項式是常見的圖不變量，在空間圖理論中具有十分重要的作用和地位.在圖多項式中，Tutte 多項式是重要的多項式，另外Tutte 多項式也可以與Chromatic 多項式[8-9]緊密聯系起來.

給定2個圖G,H，u1,v1是圖G的任意2個頂點，u2,v2是圖H的任意2個頂點，將頂點u1,u2是用一條邊連接起來，v1,v2是用n條邊連接起來（見圖1），所得到的圖記作(1,n)，n≥ 1.

圖1 圖(1,n)

本文通過減邊縮邊定義，推導出來圖(1,n)的Tutte 多項式計算公式.

T(G;x,y)通常也簡記為T(G)或TG.

定義2[11]Tutte 多項式的減邊縮邊定義：（1）給定一個圖G，G′和G′分別表示在圖G中刪掉一條邊e和沿著邊e收縮到一點的圖，且邊e既不是環邊也不是割邊，則T(G)=T(G′) +T(G′)；（2）假設圖G是由i個環邊和l個割邊組成的，則T(G)=xi yl.

定義3[12]令圖θn表示由2個頂點和n條連接這2個頂點的邊構成的圖（見圖2），也稱為s-theta 圖.

圖2 圖 nθ

給定圖G1，G2，G1UG2表示圖G1和G2的不交并，G1∨G2表示圖G1和G2的一點并.

性質1[10]395若e為圖G中的一條邊，那么

2 主要結果及證明

定理對于圖(1,n)，n≥ 1，有

其中：TG,TH分別為圖G,H的Tutte 多項式；T(G:H)為圖G,H的兩點并的Tutte 多項式.

證明對圖(1,n)的n條邊中的一條邊進行減邊縮邊的運算，再對n-1條邊進行縮邊減邊的運算，以此類推，那么有等式

成立，其中：圖Hn1-，Fn1-，En1-見圖3.

圖3 圖H n1-，Fn1-，En1-

由式（2）可知

推論圖θn的Tutte 多項式為.

證明根據定理和Tutte 多形式的定義，有

其中：圖M i(i=1,2,L,n)為一個點連接i條環邊所構成的圖，且T(Mn)=yn，T(θ1)=x. 證畢.

3 結語

本文主要研究了一類特殊連圖的Tutte 多項式，目前僅有扇圖、輪圖和Flower 圖計算出了Tutte 多項式的具體表達方式.未來還可以研究其它更多圖的Tutte 多項式的性質以及進一步探究Yamada 多項式與Tutte 多項式之間的聯系.