一類樹的伴隨多項式的分解及其補圖的色等價性

熊鵬飛，張秉儒

(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)式，同法可證如下的結論：