一类树的伴随多项式的分解及其补图的色等价性

熊鹏飞，张秉儒

(1.青海交通职业技术学院，青海 西宁 810006；2.青海师范大学数学与统计学院，青海 西宁 810008)

1 预备知识

2 图的伴随多项式的概念

设G是p的阶图,若图G的生成子图G0的所有分支是完全图，则称G0为G图的理想子图。用bi(G)表示图G的具有p-i个分支的理想子图的个数(0≤i≤p-1),由文[4]的定理15可知

(1)

这里是p=|V(G)|,(λ)k=λ(λ-1)(λ-2)…(λ-k+1)。

定义2.1[5]设G是p阶图，则图G的多项式

(2)

称为简单图G的伴随多项式，h(G,x)可以简记为h(G)。

图G的每个分支或是K1或是K2的生成子图称为图G的一个匹配，图G的一个k-匹配就是含有k条边的匹配，由G的理想子图的个数bi(G)的定义即得如下的

引理2.1[5]若G是无三角形K3的图，则bi(G)等于图G的i-匹配的数目。

定义2.2称图G与H是伴随等价的，若h(G,x)=h(H,x)；称图G是伴随唯一的，若从h(H,x)=h(G,x)推出图G与H同构，记为H≌G。

我们常用到图的伴随多项式h(G,x)的如下的基本性质：

引理2.3[7]设uv∈E(G)且uv不属于图G的任何三角形，则有

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

引理2.4[7]设图G具有k个分支G1,G2,…,Gk，则有

设G是任意的连通图，其伴随多项式h(G,x)以下简记为h(G)。并不再赘述。

根据引理2.4,我们容易推知如下的

引理2.5设G和H是任意的两个图，K1是一个孤立点，n≥2是任意的自然数，则有

(ⅰ)h(H∪nG)=h(H)h(nG)=h(H)hn(G)；

(ⅱ)h(H∪nK1)=h(H)h(nK1)=xnh(H)。

引理2.6[9-10]设n≥2是自然数，Pn表示具有n个顶点的路，则有

(ⅰ)h(Pm+1)=xh(Pm)+xh(Pm-1)

(3)

(ⅱ)h(Pm+n)=h(Pm)h(Pn)+

xh(Pm-1)h(Pn-1)

(4)

引理2.7[11]设∀k∈N,m(≥3)是自然数，Ψ(k,m)表示把星图Sk+1的唯一k度点与Pm的一个1度点重迭后得到的图,则有

(ⅰ)h(Ψ(2,m))=x2[h(Pm)+2h(Pm-1)]

(5)

(ⅱ)h(Ψ(k,m))=xk[〗h(Pm)+kh(Pm-1)]

(6)

3 几类新图的伴随多项式

引理3.1设m(≥3)是任意自然数，∀r∈N,r≥1，则有

(7)

(8)

故(7)式成立；

xh(Pm-1)h(Pm)h(Pm+1)=h(Pm+1)·

xh(Pm)[h(Pm)+2h(Pm-1)]+

xh(Pm-1)h(Pm)h(Pm+1)=

xh(Pm)h(Pm+1)[h(Pm)+3h(Pm-1)]

即(8)式也成立。

引理3.2设m(≥3)是任意自然数，∀r∈N,r≥1，δ=(r+1)m+r，则有

xh(Pm)hr-1(Pm+1)[h(Pm)+(r+1)h(Pm-1)]

(9)

证明如图3.1所示,对自然数r≥1作数学归纳法：当r=1,2时，由(7)和(8)两式知公式成立；假定公式对r-1成立，即

根据(12)式及归纳假定，我们有

xh(Pm)hr-1(Pm+1)[h(Pm)+rh(Pm-1)]+xh(Pm-1)h(Pm)hr-1(Pm+1)=

xh(Pm)hr-1(Pm+1)[h(Pm)+(r+1)h(Pm-1)]

由数学归纳法原理知，公式(9)对于任意自然数r都成立。

我们定义顶点数记号:λ=(n+1)+2-1(n+2)δ,则有

(n-1)+2-1nδ=(n+1)+2-1(n+2)δ-2-δ=λ-2-δ

2λ-1-δ=(2n+1)+(n+1)δ,(n-1)+2-1nδ=λ-2-δ

引理3.3设n(≥4)是偶数，m≥3,r≥1，δ=(r+1)m+r,λ=(n+1)+2-1(n+2)δ,则有

(10)

(11)

注意到δ=(r+1)m+r，λ-2-δ=(n-1)+2-1nδ,则由上式可知(11)式成立；

即(11)式也成立。

引理3.4设n(≥4)为偶数，r≥1，δ=(r+1)m+r，λ=(n+1)+2-1(n+2)δ,则有

(12)

(13)

(ⅱ)如图3.5所示，在图ΨT(2δ,λ-2-δ)中取边e=Vnw1,由引理2.3和引理2.4及(12)式，即得

由此可知(13)式也成立。

4 因式分解定理

定理4.1设r(≥1)是任意自然数，m∈N,m≥3，δ=(r+1)m+r，则有

(14)

(15)

证明对于∀r∈N,r≥1,m≥3，注意到h(K1)=x，由引理2.5、(9)和(6)两式，即得

即(14)式成立；根据(14)式及引理2.5，容易推知(15)成立。

定理4.2设n(≥4)为偶数，r≥1，δ=(r+1)m+r，λ=(n+1)+2-1(n+2)δ,则有

(16)

(17)

证明(ⅰ)若n(≥4)为偶数时，注意到δ=(r+1)m+r，λ=(n+1)+2-1(n+2)δ，由引理2.5、(11)和(16)两式，即得

故(16)式成立；

(ⅱ)根据引理2.4及(16)式，容易推知(17)式成立。

定理4.3设n(≥4)为偶数，r≥1，δ=(r+1)m+r，λ=(n+1)+2-1(n+2)δ,则有

(18)

(19)

证明(ⅰ)根据引理2.5、(14)和(16)两式，即得

(ⅱ)根据引理2.4及(18)式，容易推知(19)式成立。

5 图的色价性分析

在给出几类图的伴随分解的基础上，我们来讨论这些图色等价性。

证明根据(15)式知

证明根据(17)式知

仿此，根据定义2.2和引理2.2以及(19)式，同法可证如下的结论：