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

Comparison of Some Classes of Two-Variable Chromatic Polynomials

作　　者：刘莹[1] 唐晓清[2] 

机构地区：[1]邵阳学院理学与信息科学系,中国邵阳422000 [2]上海立信会计学院数学与信息学院,上海201620

出　　处：《湖南师范大学自然科学学报》2014年第6期67-72,共6页Journal of Natural Science of Hunan Normal University

基　　金：国家自然科学基金资助项目(60872060)

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

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

分 类 号：O157.5[理学—数学]