图的双变量色多项式比较研究

刘莹　唐晓清

摘 要 对图论的一些著名的双变量色多项式进行比较研究，对Tutte， Potts， Matching和Dohmen多项式，从定义、表达式的关系以及性质进行比较.特别地，对Tutte多项式的减-缩边公式，给出严格证明；对其余3种，则补充了它们各自的减-缩边公式以及证明.同时，由这些减-缩边公式得出它们各自一些特殊图的色多项式的具体计算公式，显示了减-缩边公式在简化计算方面的应用.

关键词 双变量色多项式；减-缩边公式；Pascal矩阵

中图分类号 O157.5 文献标识码 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）的连通部分数，k（E）表示图G的连通部分数，A表示边子集A所含边数，V表示顶点数.

其后，又陆续有一些学者提出一些新的双变量色多项式，比较著名的有Potts双变量色多项式，Matching双变量多项式等.最近，Dohmen等人提出新的双变量色多项式概念[2]，并提出如下色多项式计算公式：

5 结论

本文对于一些著名的双变量色多项式进行了比较研究，对有些定理给予新的证明，有些给出了相应的减缩边公式，此外，还探讨了它们之间的关系.期待这些工作能引起同行进一步的深入研究.

参考文献：

[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].兰州大学学报：自然科学版， 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.

（编辑 胡文杰）