一類特殊連圖的Tutte多項(xiàng)式

（遼寧師范大學(xué) 數(shù)學(xué)學(xué)院，遼寧 大連 116029）

1 引言及預(yù)備知識(shí)

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

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

圖1 圖(1,n)

本文通過減邊縮邊定義，推導(dǎo)出來圖(1,n)的Tutte 多項(xiàng)式計(jì)算公式.

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

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

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

圖2 圖 nθ

給定圖G1，G2，G1UG2表示圖G1和G2的不交并，G1∨G2表示圖G1和G2的一點(diǎn)并.

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

2 主要結(jié)果及證明

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

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

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

成立，其中：圖Hn1-，F(xiàn)n1-，En1-見圖3.

圖3 圖H n1-，F(xiàn)n1-，En1-

由式（2）可知

推論圖θn的Tutte 多項(xiàng)式為.

證明根據(jù)定理和Tutte 多形式的定義，有

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

3 結(jié)語(yǔ)

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