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

2013-07-22 02:52宝音
赤峰学院学报·自然科学版 2013年13期
关键词:子图等价结论

宝音

(青海民族大学蒙学系,青海西宁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)

猜你喜欢
子图等价结论
由一个简单结论联想到的数论题
等价转化
立体几何中的一个有用结论
临界完全图Ramsey数
n次自然数幂和的一个等价无穷大
基于频繁子图挖掘的数据服务Mashup推荐
结论
收敛的非线性迭代数列xn+1=g(xn)的等价数列
不含2K1+K2和C4作为导出子图的图的色数
环Fpm+uFpm+…+uk-1Fpm上常循环码的等价性