论文部分内容阅读
在研究图的相关性质及应用的很多文章中用相关的多项式不变量来刻画图类,如特征多项式,匹配多项式,色多项式,多色多项式,Tutte多项式,亏格分布多项式,全嵌入分布多项式等,如何求出图的这些多项式不变量,并通过这些多项式讨论图的相关性质成为近些年来一直关注的课题.
该文是本人于研究生阶段在图的色多项式,色唯一性,伴随多项式,图的全嵌入分布方面得到的结果的总结.
本文共分为四章:第一章综述本文所研究课题的背景、发展现况及原有结论,阐述本人所做工作.
第二章讨论图的色唯一性;在文献[18]的基础上对两类图Tn1∪Tn2∪…Tnr∪mK1和Fn1∪Fn2∪…Fnr∪mK1的补图的色唯一性进行讨论,得到结论:(1)若G=Tn1∪Tn2∪…∪Tnr∪mK1,其中Tni(li1,li2,li3)是不可约图,且(li1,li2)≠(1,1),(li1,li2)≠(1,2),则-G是色唯一的.(2)若G=Fn1∪Fn2∪…∪Fnr∪mK1,其中Fni是不可约图,ni≥6,则-G色唯一.
第三章给出两类图的伴随多项式;推广已有图Dn,Fn到两类新图Dni,Fni,得到它们的伴随多项式:h(Dni,μ)∑k≥n-i-1/2μk(k-1)![kμa1(μ)+(2k-n+i+1)a2(μ)]/(n-k-i-1)!(2k-n+i-1)!(n≥i+1)其中a1(μ)=h(Ci,μ)+h(Pi-1,μ),a2(μ)=h(Ci,μ).h(Fni,μ)=∑k≥n-2i/2μk-1(k-1)![kμa1(μ)+(2k-n+2i)a2(μ)]/(n-k-2i)!(2k-n+2i)!(n≥2i)其中a1(μ)=h2(Ci,μ)+μh2(Pi-1,μ),a2(μ)=μh(Pi-1,μ)[2h(Ci,μ)-μh(Pi-1,μ)],并讨论了当i=4时的不可约性.
第四章给出两个图类ξr1和ξ2r2的全嵌入分布多项式;通过构造这两个图类相应的覆盖矩阵,求出覆盖矩阵的秩分布多项式,从而计算出这两类图的全嵌入分布多项式:(1)图ξr1的全嵌入分布多项式为Iξr1(x,y)=r∑k=02k4r-kDr+1k(y)+(6r-4r)(x-y2)其中Drk(z)=(1+z)r-k-1Dk+1k(z)+r-1∑j=k+1z(1+z)r-j-1Djk-1(z)+2z2(k+r-2∑j=k+1(jk-1))(1+z)r-2,Dr0(z)=(1+z)r(2)图ξ2r2的全嵌入分布多项式为Iξ2r2(x,y)=L2r+1(B2r+1,y)+Iξ2r2(x)-Iξ2r2(y2)其中L2r+1(B2r+1,z)=(200z2+136z+40)L2r-1(B2r-1,z)+16z2(8z+5)r-1∑m=0(r-1m)40m80r-1-m(z+3z2)m(1+z)2r-2-2m