熊鹏飞，张秉儒

(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都成立。……