论文部分内容阅读
图的临界群和染色多项式是反映图性质的重要参数.从研究文献来看,临界群的研究是近20年的事物,由于时间不长,研究成果还不太多;而关于图的染色多项式的研究已经有很长的历史,成果已经比较多了.关于图的临界群,一个重要内容是计算其临界群.图染色多项式的研究方面有一个重要课题是尽可能多的定出染色唯一的图类.
图临界群的阶数与图的支撑树数目相等.支撑树数目不同的两个图肯定不同构,支撑树数目相同但临界群不同的两个图也肯定不同构.本文我们得到了全连边图Km∨Pn和Pm∨Pn(m≥4,n≥5)的临界群和它们的支撑树数目.判定一个图是否具有染色唯一性,至今没有好的方法.幸运的是,具有围长不超过7且同胚K4的染色唯一的图已经被完全确定,在这方面本文确定了围长为8的染色唯一的K4同胚图.下面就是本文的主要结果.
1.1全连边图Km∨Pn的临界群为Z/(m+n,an,bn)Z⊕(Z/(m+n)Z)m-2⊕Z/(m+n)an/(m+n,an,bn)Z.
1.2全连边图Km∨Pn的生成树的数目为(m+n)m-2/√m2+4m((m+2+√m2+4m)n-(m+2-√m2+4m)n).
2.1全连边图Pm∨Pn的临界群是Z/tZ⊕Z/sZ,其中参数s和t在2.3节中介绍.
2.2全连边图Pm∨Pn的生成树的数目为(分式略)
3.1围长为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).
3.2围长为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.
3.3围长为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.
3.4围长为8的K4同胚图K4(1,2,c,2,e,3)不是染色唯一的当且仅当它是K4(1,2,α,2,α+3,3)(α≥5).
3.5围长为8的K4同胚图K4(1,2,c,3,e,2)是染色唯一的.
3.6围长为8的K4同胚图K4(2,2,4,d,e,f)不是染色唯一的当且仅当它是K4(2,2,4,β,1,β+2)(β≥5).