|
图的临界群和染色多项式是反映图性质的重要参数.从研究文献来看,临界群的研究是近20年的事物,由于时间不长,研究成果还不太多；而关于图的染色多项式的研究已经有很长的历史,成果已经比较多了.关于图的临界群,一个重要内容是计算其临界群.图染色多项式的研究方面有一个重要课题是尽可能多的定出染色唯一的图类.图临界群的阶数与图的支撑树数目相等,但生成树数目不同的两个图肯定不同构,生成树数目相同的两个图若临界群不同肯定也不同构.本文我们得到了全连边图Km∨Pn和Pm∨Pn(m≥4,n≥5)的临界群,结果如下：全连边图Km∨Pn的临界群为它的支撑树的数目为全连边图Pm∨Pn的临界群是Z/tZ(?)Z/sZ,其中t=(bn-2,cd-1,am-2),s=它的支撑树的数目为这里出现的参数an,bn,c,d表达式具有一致性,具体表达式在正文给出.判定一个图是否具有染色唯一性,至今没有好的算法.到目前为止,被确定具有染色唯一性的图类并不多.幸运的是,具有围长不超过7且同胚K4的染色唯一的图已经被完全确定,在这方面本文确定了围长为8的染色唯一的K4同胚图,相关的具体结果为：围长为8的K4同胚图G=K4(2,3,3,d,e,f)不是色唯一的当且仅当G同构于K4(2,3,3,1,6,α)(α≥6),K4(2,3,3,1,β,β+2)(β≥4),或者K4(2,3,3,1,5,6).围长为8的K4同胚图G=K4(1,2,5,d,e,f)不是染色唯一的当且仅当G同构于下面的图：K4(1,2,5,α,α+6,α+1)(α≥2),K4(1,2,5,β+2,β,β+5)(β≥2),K4(1,2,5,γ,γ+1,γ+6)(γ≥3),K4(1,2,5,δ+5,δ,δ+2)(δ≥3),K4(1,2,5,σ,σ-1,σ+3)(σ≥3),K4(1,2,5,η+2,η+2,η)(η≥3),K4(1,2,5,4,λ,3)(λ≥4),K4(1,2,5,4,3,7),K4(1,2,5,4,4,7),K4(1,2,5,4,6,4)其中参数d,e,f都不等于1.围长为8的K4同胚图K4(1,3,4,d,e,f)不是染色唯一的当且仅当它是下面一些K4同胚图：K4(1,3,4,α,α+1,2)(α≥4),K4(1,3,4,β,β+1,β+4)(β≥2),K4(1,3,4,γ+2,γ,γ+4)(γ≥2),K4(1,3,4,ε+2,ε+3,ε)(ε≥2),K4(1,3,4,η,η-5,η+1)(η≥2),K4(1,3,4,6,2,6),K4(1,3,4,2,5,8),K4(1,3,4,2,7,5).其中参数d,e,f的值均大于1.围长为8的K4同胚图K4(1,2,c,2,e,3)不是染色唯一的当且仅当它是K4(1,2,α,2,α+3,3)(α≥5).围长为8的K4同胚图K4(1,2,c,3,e,2)是染色唯一的.围长为8的K4同胚图K4(2,2,4,d,e,f)不是染色唯一的当且仅当它是K4(2,2,4,β,1,β+2)(β≥5).
|