宝音

(青海民族大学蒙学系，青海西宁810007)

宝音

(青海民族大学蒙学系，青海西宁810007)

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

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

我们仅考虑简单图，用V(G)和E(G)分别表示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。

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的任何三角形，则

引理2［3］:设图G有k个分支G1，G2，…GK，则h(G，x)=h(G1，x)h(G2，x)…h(GK，x)。

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

引理5［6］:(i)图G与H是伴随等价的当且仅当与式色等价的;

(ii)图G是伴随唯一的当且仅当G 色唯一的。

引理6［6］:设Sn+1是n+1阶的星图，则h(Sn+1，x)=xh(Sn，x)+xn

引理7［7］:设r，m∉N;r≥2;m≥1则

图1:图

图2:图

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

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

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

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

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

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

2 因式分解与色性分析

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

证明:由引理2，引理4，引理8(iii)和引理9(iii)，即得结论