图簇的伴随多项式的因式分解及其补图的色等价性

宝音

（青海民族大学蒙学系，青海西宁810007）

宝音

（青海民族大学蒙学系，青海西宁810007）

本文利用图的伴随多项式的性质及其伴随分解的图论方法,讨论了型图的伴随多项式的因式分解，进而证明了在不同条件下这类图的补图的色等价性.

色多项式；伴随多项式；因式分解；色等价性

我们仅考虑简单图，用V（G）和E（G）分别表示G的顶点集和边集表示图G的补图，G1∪G2表示图G1与G2和的点不重并.NG表示N个图G的点不重并.未加说明的记号和术语均来自文[1].设P（G，Λ）是图G的色多项式，称图G与H是色等价的，若P（G，λ）=P（H，λ）；称图G是色唯一的，若从P（H，λ）=P（G，λ）推出图H与G同构，记为H≌G.本文将图G(Pn

r)推广到，并证明了图簇的伴随多项式的伴随等价，据此讨论了)类图簇的伴随多项式的因式分解问题，给出并证明了它们的补图的色等价图的结构特征.

1 预备知识

设G是n阶图，若图G的生成子图M的每个分支都是完全图，则称M是G的理想子图，用N(G,K)表示图G的具有k个分支的理想子图的个数，则图的色多项式可以表示为[3]，设G是n阶图，

n=|v(G)|？,其中(λ)k=λ(λ-1)(λ-2)…(λ-k+1).定义1[3]设G是n阶图，则多项式

称为图G的伴随多项式并且简记为h(G).

引理1[3]设UV∈E(G)且UV不属于G的任何三角形，则

h(G,x)=h(G-uv,x)+xh(G-{u,v},x)

引理2[3]设图G有k个分支G1,G2,…,GK,则h(G,x)=h (G1,x)h(G2,x)…h(GK,x).

引理3[4]设Pn和Cn分别表示具有n个顶点的路和圈，则有

引理4[5]设G是任意图，则h(G∪k1,x)=h(G,x)hn(k1,x) =xnh(G,x).

引理5[6](i)图G与H是伴随等价的当且仅当G与H式色等价的；

引理6[6]设Sn+1是n+1阶的星图，则h(Sn+1,x)=xh(Sn,x)+xn

引理7[7]设G是p阶连通的对称图，p≥2,p≥i≥1；vi∈v(G);r≥1;m≥2

引理8[7]设G是p阶连通的对称图，p≥2,p≥i≥1；vivj∈E(G);r≥1;

引理9[8]设m,n∈N,m≥1,n≥1，则有

引理10[8]设t≥1的任意自然数而q≥3是给定的正奇数，并且m,n∈N,m≥1,n≥1，则有

定义2设G是p阶连通图，把Sm+1中的第m个顶点分别与图(其中记号及其对应的图簇均见文[2])的每个点重迭后得到的图记为；把图中的每一个Pn+1的每一个点与图Sm+1中每一个m个顶点分别重迭后得到的图记为

图1 图

图2 图

引理11设r≥i≥3;r≥1;n≥2则

对公式(6)提出公项,逐项递推和式(ii)得

用数学归纳法来可以证明公式(5)对一切自然数都成立.

引理12设r≥i≥3;r≥1;n≥2则

证明（i）当r=1时，在图h(PSmP(1,n+1))中均取uv=v00v11，则由引理1和引理2可得到式（7）

(ii)当r=2时，在图h(PSmP(2,n+1))中均取uv=v00v11，则由引理1和引理2和(i)得到

(iii)在图h(PSmP(r,n+1))中均取uv=v00v11，则由引理1和引理2得到

对公式(10)提出公项,逐项递推和式(ii)得

用数学归纳法来可以证明公式(9)对一切自然数都成立.

2 因式分解与色性分析

定理1设G是不含三角形的任意p阶连通图，r≥i≥3;r≥1;n≥2则有

证明由引理2，引理4，引理11(iii)和引理12(iii)，即得结论

因此，即(i)的结论成立.由(i)式及引理2和引理4容易推知(ii)式也成立.

推理1设G是不含三角形的任意p阶连通图，则有

定理2设G是p阶连通的对称图，p≥2,p≥i≥1；vi∈v(G);r=m≥2

证明由引理2，引理4，引理7和定理1，即得结论

因此，即(i)得结论成立.由(i)式及引理2和引理4容易推知(ii)式也成立.

定理3设G是p阶连通的对称图，p≥2,p≥i≥1；vivj∈E(G);r≥1;

证明由引理2，引理4，引理8和定理2，即得结论.

定理4设m,n,r∈N,m≥2,n≥2,r≥2，则有

证明由引理2，引理4，引理9和定理1，即得结论.

因此，即(i)的结论成立.由(i)式及引理2和引理4容易推知(ii)式也成立.

定理5设G是不含三角形的任意p阶连通图，t≥1的任意自然数而q≥3是给定的正奇数，r≥i≥3;r≥1;n≥2则有

证明由引理2，引理4，引理10和定理1，即得结论.

因此，即(i)的结论成立.由(i)式及引理2和引理4容易推知(ii)式也成立.

类似地，根据引理4，引理5和定理2，定理3，可证如下的结论

定理7设G是p阶连通的对称图，p≥2,p≥i≥1；vi∈v(G);;r=m≥2

定理8设G是p阶连通的对称图，p≥2,p≥i≥1；vivj∈E(G);;r≥1

定理9设m,n,r∈N,m≥2,n≥2,r≥2，则图簇

定理10设G是不含三角形的任意p阶连通图，t≥1的任意自然数而q≥3是给定的正奇数，r≥i≥3;r≥1;n≥2则图簇二者的补图是色等价的.

〔1〕Harary.Graph,theory[M].Addison Wesley,1969.

〔3〕刘儒英.求图的色多项式的一种新方法及应用[J].科学通报,1987，32,77.

〔4〕刘儒英.关于两类图的色多项式[J].科学通报,1987（32）：236.

〔5〕刘儒英.Pq-1的补图的色唯一性[J].数学研究与评论, 1994，14（3）：469-472.

〔6〕宝音，张秉儒.SP(i)类图簇的伴随多项式的因式分解及其色性分析[J].西南师范大学学报（自然科学版）,2004，29（4）：573-577.

〔7〕张秉儒.图的伴随多项式的因式分解定理及应用[J].数学学报,2005，48（1）：125-132.

〔8〕侯海存，张秉儒.一类新的图簇的伴随分解定理及其补图的色等价性[J].西南师范大学学报（自然科学版）,2010，35（4）：69-73.

O157.5

A

1673-260X（2013）07-0001-04

青海省自然科学基金资助项目(2011-Z-911)