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

劉瑩　唐曉清

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

關(guān)鍵詞 雙變量色多項式；減-縮邊公式；Pascal矩陣

中圖分類號 O157.5 文獻(xiàn)標(biāo)識碼 A 文章編號 1000-2537（2014）06-0067-06

Abstract 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.

Key words two-variable chromatic polynomial； reduce-contract edge formula； Pascal matrix

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

T（G；x，y）=∑AE（x-1）k（A）-k（E）（y-1）A+k（A）-V （1）

這里，G=（V，E），V和E分別表示圖G的頂點集和邊集，k（A）表示邊子集A和V組成的子圖（V，A）的連通部分?jǐn)?shù)，k（E）表示圖G的連通部分?jǐn)?shù)，A表示邊子集A所含邊數(shù)，V表示頂點數(shù).

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

5 結(jié)論

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

參考文獻(xiàn)：

[1] TUTTE W T. Graph theory[M].Cambridge： Cambridge University Press， 2001.

[2] DOHMEN K， PNITZ 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].蘭州大學(xué)學(xué)報：自然科學(xué)版， 2012，48（2）：106-112.

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

[5] 劉念祖，唐曉清，王漢興.正則q-樹根圖的雙概率可靠性探究[J].西南師范大學(xué)學(xué)報：自然科學(xué)版，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] 唐曉清，譚明純.簡單序約束條件下的參數(shù)估計的EM方法 [J].湖南工程學(xué)院學(xué)報， 2010，20（1）：61-64.

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

[10] 唐曉清，白延琴，劉念祖，等. 基于隨機矩陣?yán)碚摰腗arkowitz組合投資模型[J].上海大學(xué)學(xué)報：自然科學(xué)版， 2013，19（3）：293-297.

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

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

（編輯 胡文杰）