论文部分内容阅读
图G的独立多项式I(G；x)=∑k=0α(G)sk·xk,表示基数为k的独立集数目,其中k：∈{1…,a(G)},α(G)是图G的极大独立集的数目.在本文中我们探讨独立多项式,(G；x)的一些重要性质,并得到以下结果：(1)对于树或者是单圈图,如果图G是围长g≥6(或者g≥5)和G≠qC7(或者G≠gK2)的良好覆盖图(非常良好覆盖图),其中g是任意正整数,有,(G;-1)=0.即对于图G,偶数阶独立集和奇数阶独立集的数目是相等的.(2)存在图序列G1,G2,…,Gn,…,使得|I(Gn+1；-1)|-|(Gn+1;-1)|=2n,n=1,2,….也就是说存在图序列,当圈秩数增加1时,图的偶数阶独立集与奇数阶独立集差的绝对值是以指数级增加的；另一方面,存在图序列H1,H2,…,Hn,使得|I(Hn;-1)|≤M(M>0),n=1,2,….即存在图序列,当圈秩数增加时,图的偶数阶独立集与奇数阶独立集数值差不大于数M.(3)对于平面基图G(没有垂点),当β(G)=2时,证明了|I(G;-1)|≤2β(G)-1.证明了Levit和Mandrescu提出的猜想：对任意满足|q|≤2β的正整数β和整数q,存在连通图G,有圈秩数β(G)=β和I(G；-1)=q.