фs-型图簇的伴随分解及其色性分析

《фs-型图簇的伴随分解及其色性分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2013年12月纯粹数学与应用数学Dec．2013第29卷第6期PureandAppliedMathematicsVb1．29NO．6s．型图簇的伴随分解及其色性分析索南仁欠，一，李生刚(1．陕西师范大学数学与信息科学学院，陕西西安710062；2．青海师范大学数学系，青海西宁810008)摘要：运用图的伴随多项式的性质，讨论了图簇s((几+1)，no)u2的伴随多项式的因式分解定理，进而证明了它们的补图的色等价性．关键词：色多项式；伴随多项式；因式分解；色等价性中图分类号：O157．5文献标识码：A文章编号：1008—5513(2013)06—

2、0551—08DOI：10．3969／j．issn．1008—5513．2013．06．0011预备知识及准备工作本文仅考虑简单图，用v(a)和E(G)分别表示一个图G的顶点集和边集，用表示图G的补图，用K1表示一个孤立点，用Gu日表示图G和日的点不重并，用nG表示佗个图G的点不重并．其余未加解释和说明的术语和记号均来自参考文献[1_16]．若P阶图G的生成子图Go的每个分支都是完全图，则称Go是G的理想子图．用bi(G)表示图G的具有P—i个分支的理想子图的个数f0i

3、为P阶图G的伴随多项式：p—lh(G，)=∑bi(G)xp(1)i=O(2)称图G与图日是伴随等价的是指它们满足h(a)=(日)；称图G是伴随唯一的是指当h(G)=h(H)时有hG成立．引理1．1图G与图日伴随等价的充要条件是和百色等价：图G是伴随唯一的充要条件是是色唯一的．引理1．2[11]设UV∈E(G)且UV不属于图G的任何三角形，则有h(a，)=h(G—，)+xh(G一{，)，X)收稿日期：2013—10—08．基金项目：国家自然科学基金(11061026，11071151)．作者简介：索南仁欠(1969一)，博士生，教授，研究方向：计算

4、数学，代数组合论第6期索南仁欠等：s．型图簇的伴随分解及其色性分析553(礤州))=(碥)((品)(磅)+2x州(磙_1)))．(6)引理1．6设n，r∈N，n2，l，=r+1，则，(s(2，n))=()(()(焉)+2x2r+i(礞_1)))，(7)(s(kcr,n~))=hk-l(S~)(()()+x2r+lh(球))．(8)证明如图3所示，在图s(2，no)和s(，n仃)中均取边e=UlVl，则由引理1．2和引理1．3依次得(s(20"~nO))=()(礞+1))+x2r+lh(礞_1))，(9)h(s(，n))=h()h(s((一1)，佗

5、))+x2r+lh南一()(尸一1))．(10)由(9)，(3)式可得(7)式．根据(7)式和(10)式，用数学归纳法(k2)容易证明(8)式．引理1．7设k，n，r∈N，k2，n2，t厂1，=r+1，则h(s(2，))=()(+1))，(11)(s(2，(2q一1)))=()(q)．(12)证明由(7)式和(4)式可证明(11)式．令n=2kq一1，则由(11)式可得(12)式．引理1-8设k，n，r∈，k2，n2，r1，：r+1，则(s((n+1)，几))=(礞)(()(磁)+3x2r+lh(礞-1)))，(13)(s((七礼+1)，礼))=

6、h()(()^()+(2+1)x2r+1(尸一1)))．(14)证明如图4所示，当=1时取边el=乱l1和e2=仳u1，令=_[e1，e2]．，并且取定一边运用引理1．2和引理1．3，则可得h(s((n+1)，佗))=九(s((n+1))一e)-~X2r+1九(磁)九(碥_1))=((s((礼+1))一)+2r+1(焉)(磁_1)))+2r+1(磁)^(礞_1))=九(焉u礞+1))+2x2r+l(焉)(礞_1))．(15)由引理1．3及(15)和(3)两式知：h(s((礼+1)，no))=九(磅)(礞+1))+2x2r+l()九(_1))=(碥

7、)(()(磅)+32r+1(_1)))．554纯粹数学与应用数学第29卷如图4所示，在图s((礼+1)，nty)中，取边el=~tv11和e2=UVl扎，并令=J[el，e2}．注意到图((佗+1)，nO")一s2就是图us(((七一1)n+1)，nO")由引理1．2和引理1．3得(s((n+1)，n))：^(西s((礼+1))一e)+2r+1H(礞)(礞-1))=((西s((佗+1))一)+2r+1()(礞))+2r+1(礞)(礞_1))：h(us(((一1)n+1)仃，仉))+2x2r+lh膏一()(砾一))．冉由引理1．3得h(oS((kn

8、+1)，n))=h()((((一1)佗+1)s)+2x。r+h一()h(礞一1))．(16)运用(13)和(16)两式，对自然数(2)作