圖的雙變量色多項式比較研究

劉 瑩,唐曉清

(1.邵陽學院理學與信息科學系,中國 邵陽 422000；2.上海立信會計學院數學與信息學院，上海 201620)

圖的雙變量色多項式比較研究

劉 瑩1,唐曉清2*

(1.邵陽學院理學與信息科學系,中國 邵陽 422000；2.上海立信會計學院數學與信息學院，上海 201620)

對圖論的一些著名的雙變量色多項式進行比較研究，對Tutte, Potts, Matching和Dohmen多項式，從定義、表達式的關系以及性質進行比較．特別地，對Tutte多項式的減-縮邊公式，給出嚴格證明；對其余3種，則補充了它們各自的減-縮邊公式以及證明．同時，由這些減-縮邊公式得出它們各自一些特殊圖的色多項式的具體計算公式，顯示了減-縮邊公式在簡化計算方面的應用．

雙變量色多項式；減-縮邊公式；Pascal矩陣

色多項式一直是圖論的一個重要研究方向．為了解決單變量色多項式中存在的一些問題，Tutte最先提出雙變量色多項式[1]，他的定義為：

(1)

這里，G=(V,E),V和E分別表示圖G的頂點集和邊集，k(A)表示邊子集A和V組成的子圖(V,A)的連通部分數，k(E)表示圖G的連通部分數，|A|表示邊子集A所含邊數，|V|表示頂點數．

其后，又陸續有一些學者提出一些新的雙變量色多項式，比較著名的有Potts雙變量色多項式，Matching雙變量多項式等．最近，Dohmen等人提出新的雙變量色多項式概念[2],并提出如下色多項式計算公式：

(2)

對于該新雙變量色多項式，作者已經提出了相應的減-縮邊公式[3],即：

P(G;x,y)=P(G-e;x,y)-P(G/e;x,y)+(x-y)·P(G-{u,v};x,y)

(3)

眾所周知，減-縮邊公式對色多項式的計算非常重要，本文對這些有代表性的雙變量色多項式的減-縮邊公式進行進一步的探討．

1 Tutte雙變量色多項式的減-縮邊公式

Tutte雙變量色多項式已提出很久了，但是，由于它的變量意義不太明顯，故而，所引起的關注不很多．現在，本文嘗試討論有關問題．

定理1對于Tutte雙變量色多項式，有如下減-縮邊公式[4]：

(4)

注橋即有一個端點的度數為1的邊．

證分如下三種情況：

Ⅰ.當邊e是橋時，A=A′+{e},k(A)=k(A′),k(E)=k(E′)-1,|V|=|V′|+1,由式(1)有

Ⅱ.當邊e是環時，A=A′+{e},k(A)=k(A′),k(E)=k(E′),|V|=|V′|，由式(1)有

Ⅲ.當邊e非橋非環時，有如下兩種情況：

當取邊e時，A=A′+{e},k(A)+1=k(A′),k(E)+1=k(E′),|V|=|V′|；

當不取邊e時，A=A′+{e},k(A)=k(A′),k(E)=k(E′),|V|=|V′|+1，由式(1)有

T(G-e;x,y)+T(G/e;x,y).

綜合以上討論可知，Tutte多項式的減縮邊公式(4)恒成立．

減-縮邊公式的應用

利用減-縮邊公式(4)，可方便地求得任何圖的Tutte雙變量色多項式．

(1) 有n個頂點的簡單(沒有重邊和環)樹圖(表示為Tn)，則有：

T(Tn;x,y)=xn-1,(n≥2).

(2) 有n個頂點的簡單圖圈(表示為Cn)，則有：

(3) 對2個頂點之間有n條重邊的圖，稱n連接圖(Link)(表示為Ln), 則有：

注對于沒有環的單個頂點，稱為空圖(Null)(表示為φ)，令T(φ;x,y)=1．

(4) 對有n個頂點的扇圖(表示為Fn), 則有：

一些簡單的扇圖的Tutte雙變量色多項式如下：

T(F3;x,y)=y+x+x2,

T(F4;x,y)=y+x+y2+2xy+2x2+x3.

(5) 對有n個頂點的輪圖(表示為Wn),則有：

[T(F3;x,y)+yT(L2;x,y)]+yn-4[T(F3;x,y)+yT(L2;x,y)+yT(L3;x,y)].

一些簡單的輪圖的Tutte雙變量色多項式如下：

T(W4;x,y)=2y+2x+3y2+3x2+4xy+y3+x3,

T(W5;x,y)=3x+3y+9xy+6y2+4y3+y4+4xy2+6x2+4x2y+4x3+x4.

2 Potts剖分雙變量色多項式

Potts雙變量色多項式的表達式[6]如下：

(5)

同樣，k(A)表示圖G=(V,E)的邊子集A和V組成的子圖(V,A)的連通部分數，|A|表示邊子集A所含邊數．

比較(1)和(5)，明顯有：

T(G;x,y)=(x-1)-k(E)(y-1)-|V|·Z(G;(x-1)(y-1),y-1),

(6)

從定義(5)，易得：Z(P1;x,y)=x，再令Z(φ;x,y)=1.

定理2對于Potts雙變量色多項式計算公式，有如下減邊公式：

Z(G;x,y)=Z(G-e;x,y)+y·Z(G/e;x,y)

(7)

證邊e有兩種情形：

Ⅰ.e?A，此時，A=A′，k(A)=k(A′),|A|=|A′|；

Ⅱ.e∈A，此時，A=A′∪{e}，k(A)=k(A′),|A|=|A′|+1．

綜合這兩種情形，故而：

Z(G-e;x,y)+y·Z(G/e;x,y).

一些特殊圖的Potts色多項式計算公式

(1) 有n個頂點的路圖(表示為Pn)的Potts色多項式的計算公式:

Z(Pn,x,y)=x·Z(Pn-1;x,y)+y·Z(Pn-1;x,y)=(x+y)·Z(Pn-1;x,y)=

(x+y)n-1·Z(P1;x,y)=x(x+y)n-1,n≥1.

(2) 有n個頂點的圈圖(表示為Cn)的Potts色多項式的計算公式:

Z(Cn;x,y)=Z(Pn;x,y)+y·Z(Cn-1;x,y)=Z(Pn;x,y)+y·[Z(Pn-1;x,y)+y·Z(Cn-2;x,y)]=

而Z(C3;x,y)=x3+3x2y+3xy2+xy3,

經過反復迭代以后，可以得到圈圖的計算公式：

(3) 對有n個頂點的扇圖(表示為Fn),則有如下Potts計算公式：

[x3+4x2y+(x2y2+5xy2)+4xy3+xy4],n≥6.

下面是一些簡單的扇圖計算式

Z(F4;x,y)=x4+5x3y+10x2y2+2x2y3+8xy3+5xy4+xy5.

同樣，圈圖也有這樣類似的表達式

3 Matching雙變量色多項式

對于圖G=(V,E)，設|V|=n，ai是圖G的i-匹配數[7]，則匹配雙變量色多項式為：

(8)

定理3對于匹配雙變量色多項式，有如下減邊公式：

M(G;x,y)=M(G-e;x,y)+yM(G-{u,v};x,y).

(9)

證由于邊e=(uv)，因此匹配數考慮兩種情形：

Ⅰ.e?M；

Ⅱ.e∈M，此時，頂點{u,v}飽和．

綜合這兩種情形，有

M(G-e;x,y)+y·M(G-{u,v};x,y).

一些特殊圖的匹配色多項式計算公式

(1) 有n個頂點的路圖(表示為Pn)的Matching色多項式的計算公式:

M(Pn;x,y)=x·M(Pn-1;x,y)+yM(Pn-2;x,y),并且，由于M(φ;x,y)=1;M(P1;x,y)=x迭代后可以得到任何路圖的色多項式，下面是一些簡單的路圖計算式．

M(P2;x,y)=x2+y,M(P3;x,y)=x3+2xy.

(2) 有n個頂點的圈圖(表示為Cn)的Matching色多項式的計算公式:

M(Cn;x,y)=M(Pn;x,y)+y·M(Pn-2;x,y),迭代后可以得到任何圈圖的色多項式．下面是一些簡單的圈圖計算式．

M(C3;x,y)=x3+3xy,M(C4;x,y)=x4+4x2y+2y2.

(3) 對有n個頂點的扇圖(表示為Fn),則有如下Matching色多項式計算公式：

M(Fn;x,y)=x·M(Fn-1;x,y)+y·M(Pn-2;x,y)+y·M(Fn-2;x,y),n≥5

并且，M(F3;x,y)=M(C3;x,y)=x3+3xy.下面是一些簡單的扇圖計算式

M(F4;x,y)=x4+5x2y+2y2,M(F5;x,y)=x5+7x3y+8xy2.

(4) 對有n個頂點的輪圖(表示為Wn)的Matching色多項式的計算公式：

M(Wn;x,y)=M(Fn;x,y)+y·M(Fn-2;x,y),n≥5

下面是一些簡單的輪圖計算式

M(W4;x,y)=x4+6x2y+3y2,M(W5;x,y)=x5+8x3y+10xy2.

(5) 對有n個頂點的完全圖(表示為Kn)的Matching色多項式的計算公式：

M(Kn;x,y)=x·M(Kn-1;x,y)+(n-1)y·M(Kn-2;x,y)

下面是一些簡單的完全圖計算式

M(K3;x,y)=x3+3xy,M(K4;x,y)=x4+6x2y+3y2.

(6) 對分別有m,n個頂點的完全二部圖(表示為Km,n)的Matching色多項式的計算公式:

M(Km,n;x,y)=x·M(Km-1,n;x,y)+ny·M(Km-1,n-1;x,y)

下面是一些簡單的完全二部圖計算式

M(K3,2;x,y)=x5+6x3y+6xy2,M(K3,3;x,y)=x6+9x4y+18x2y2+6y3.

4 Dohmen雙變量色多項式

我們已對Dohmen雙變量色多項式得出了對應的減-縮邊公式，詳見文獻[3]．現在，本文對該公式給出新的證明．

定理4對于Dohmen新雙變量色多項式計算公式，有如下減邊公式[3]：

P(G;x,y)=P(G-e;x,y)-P(G/e;x,y)+(x-y)·P(G-{u,v};x,y) (10)

其中，頂點u∈V,v∈V，而且，邊(uv)=e∈E

證由定義(2)，有

即，有

P(G;x,y)=x[P(G-{u};x,y)+P(G-{v};x,y)]-y[P(G-{u};x,y)+P(G-{v};x,y)]+

P(G-{v};x,y)]-x[P(G-{u};x,y)+P(G-{v};x,y)-P(G-{u,v};x,y)]+

(x-y)[P(G-{u};x,y)+P(G-{v};x,y)]+(x-y)2P(G-{u,v};x,y)+

P(G-{v};x,y)+(x-y)P(G-{u,v};x,y)]=P(G-e;x,y)-P(G/e;x,y)+

(x-y)P(G-{u,v};x,y).

利用該減-縮邊公式，易得一些特殊圖的Dohmen色多項式計算公式[8-14]．

(1) 對有n個頂點的完全圖(表示為Kn)的Dohmen色多項式計算公式：

P(Kn;x,y)=yP(Kn-1;x-1,y-1)+(x-y)P(Kn-1;x,y).

(2) 對有n個頂點的輪圖(表示為Wn)的Dohmen色多項式計算公式：

P(Wn;x,y)=yP(Cn-1;x-1,y-1)+(x-y)P(Cn-1;x,y).

(3) 對有n個頂點的路圖(表示為Pn)的Dohmen色多項式的計算公式:

注對于沒有頂點的空圖φ,我們令P(φ,x,y)=1

(4) 對有n個頂點的圈圖(表示為Cn)的Dohmen色多項式計算公式:

(5) 對分別有m,n個頂點的完全二部圖(表示為Km,n)的Dohmen色多項式計算公式:

(6) 對有n個頂點的扇圖(表示為Fn),則有如下DOHMEN色多項式計算公式：

P(Fn;x,y)=P(Wn;x,y)+P(Wn-1;x,y)-(x-y)·P(Fn-2;x,y) .

或者，有

P(Fn;x,y)=(x-2)·P(Fn-1;x,y)+(x-y)·[P(Fn-2;x,y)+P(Pn-2;x,y)].

5 結論

本文對于一些著名的雙變量色多項式進行了比較研究，對有些定理給予新的證明，有些給出了相應的減縮邊公式，此外，還探討了它們之間的關系．期待這些工作能引起同行進一步的深入研究．

[1] TUTTE W T. Graph theory[M].Cambridge: Cambridge University Press, 2001.

[2] DOHMEN K, P?NITZ A, TITTMANN P. A new two-variable generalization of the chromatic polynomial[J].Discrete Math Theor Comput Sci, 2003,6(2):69-89.

[3] 唐曉清，劉念祖，王漢興，等.圖的一類新雙變量色多項式[J].蘭州大學學報：自然科學版，2012,48(2)：106-112.

[4] 唐曉清，劉念祖，王漢興，等.正則樹的雙變量色多項式研究[J].應用數學學報，2013,36(4)：761-768.

[5] 劉念祖，唐曉清，王漢興.正則q-樹根圖的雙概率可靠性探究[J].西南師范大學學報：自然科學版，2013,38(12)：24-27.

[6] WELSH D. The Tutte polynomial[J].Random Structures Algorithms, 1999,15(3-4):210-228.

[7] AVERBOUCH I, MAKOWSKY J. The complexity of multivariate matching polynomials, January 2007. Preprint.

[8] 唐曉清，譚明純.簡單序約束條件下的參數估計的EM方法 [J].湖南工程學院學報，2010,20(1):61-64.

[9] 王漢興，劉念祖，唐曉清，等.基于數學模型的混泥土泵車液壓系統的Simulink動態仿真 [J].重慶理工大學學報：自然科學版，2012,26(9):1-7.

[10] 唐曉清，白延琴，劉念祖,等. 基于隨機矩陣理論的Markowitz組合投資模型[J].上海大學學報：自然科學版, 2013,19(3):293-297.

[11] 沈小玲，侯耀平.最大度和次大度相等的雙星樹由它的Laplacian譜確定[J] .湖南師范大學自然科學學報, 2007,30(3):22-25.

[12] 沈小玲，侯耀平.毛毛蟲圖的r次冪的最小斜秩[J].湖南師范大學自然科學學報, 2014,37(4):87-91.

(編輯 胡文杰)

Comparison of Some Classes of Two-Variable Chromatic Polynomials

LIUYing1,TANGXiao-qing2,3*

(1.Department of Science and Information Science, Shaoyang University, Shaoyang 422000,China;2.School of Mathematics and Information, Shanghai Lixin University of Commerce,Shanghai 201620, China)

By comparing theTutte, Potts, Matching and Dohmen two-variable chromatic polynomials, the present work studied famous two-variable chromatic polynomials of graph. Their properties and the relationship between those definitions are investigated. Especially, a grid proof to reduce-contract edge formula of Tutte, as well as the others reduce-contract edge formulas and proofs are presented. Moreover, we studied some concrete compute formulas of special graphs to each of them based on those reduce-contract edge formulas, and those reduce-contract edge formulas show the application in simplifying calculation.

two-variable chromatic polynomial; reduce-contract edge formula; Pascal matrix

2013-03-26

國家自然科學基金資助項目(60872060)

*

,E-mail：tangxiaoqing5168@163.com

O157.5

A

1000-2537(2014)06-0067-06