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

熊鵬飛，張秉儒

(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，則有

h(G，x)=h(G1x)h(G2,x)…h(Gk,x)=

設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 幾類新圖的伴隨多項式

圖1 圖

圖2 圖ΨK(2,λ)，λ=n+2-1(n+1)δ

圖3 圖

圖4 圖

圖5 圖ΨT(2δ,(λ+1)+2)

圖6 圖

引理3.1設m(≥3)是任意自然數，?r∈N,r≥1，則有

(7)

(8)

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

故(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-1)h(Pm)hr-1(Pm+1)=h(Pm+1)·

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

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

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+2-1(n+1)δ,則有

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

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

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

引理3.3設n(≥3)是奇數，m≥3,r≥1，δ=(r+1)m+r,λ=n+2-1(n+1)δ,則有

h(Pm-1)hr(Pm+1)h(ΨK(1,λ-2-δ))]

(11)

2h(Pm-1)hr(Pm+1)h(ΨK(1,λ-2-δ))]

(12)

證明(ⅰ)如圖3.2所示，在圖ΨK(1,n+2-1(n+1)δ)中取邊e=V1W1,則由引理2.3和引理2.4，并注意到λ=n+2-1(n+1)δ，λ-2-δ=(n-2)+2-1(n-1)δ，我們有

h(Pm-1)hr(Pm+1)h(ΨK(1,λ-2-δ))]

故(11)式成立；

(ⅱ)如圖3.2所示，在圖ΨK(2,n+2-1(n+1)δ)中均取邊e=V1W1,由引理2.3和引理2.4及(11)式，并注意到λ=n+2-1(n+1)δ，λ-2-δ=(n-2)+2-1(n-1)δ，我們有

即(12)式也成立。

引理3.4設n(≥3)是奇數，m≥3,r≥1，δ=(r+1)m+r,λ=n+2-1(n+1)δ,則有

(13)

(14)

由此可知(13)式成立；

=x[xh(ΨK(2,λ))+

故(14)式也成立。

引理3.5設n(≥3)是奇數，m≥3,r≥1，δ=(r+1)m+r，λ=n+2-1(n+1)δ,則有

xh(Pm-1)hr(Pm+1)h(ΨK(2，λ))

(15)

(ⅱ)h(ΨT(2δ,(λ+1)+2))=

2xh(Pm-1)hr(Pm+1)h(ΨK(2，λ))]

(16)

證明(ⅰ)當n為奇數時，n+1為偶數，如圖3.5所示，在圖ΨT(δ,λ+1+δ)中取邊e=w1Vn+1，由引理2.3和引理2.4，即得

xh(Pm-1)hr(Pm+1)h(ΨK(2，λ))

這里δ=(r+1)m+r，λ=n+2-1(n+1)δ,故(15)式成立；

(ⅱ)如圖3.5所示，在圖ΨT(2δ,λ+1+δ)中取邊e=w1Vn+1，由引理2.3和引理2.4，即得

xh(Pm-1)hr(Pm+1)h(ΨK(2，λ))+

xh(Pm-1)hr(Pm+1)h(ΨK(2，λ))]=

2xh(Pm-1)hr(Pm+1)h(ΨK(2，λ))]

這里δ=(r+1)m+r，λ=n+2-1(n+1)δ,故(16)式成立。

引理3.6設n(≥3)為奇數，r≥1，δ=(r+1)m+r，λ=n+2-1(n+1)δ,則有

(17)

2xh(Pm-1)hr(Pm+1)h(ΨK(2,λ))]

(18)

證明(ⅰ)如圖3.4所示，當n為奇數時，n+1為偶數，則d(Vn)=r+3,d(Vn+1)=2,

這里δ=(r+1)m+r，λ=n+2-1(n+1)δ,λ-2-δ=(n-2)+2-1(n-1)δ，故(17)式成立；

xh(Pm-1)hr(Pm+1)h(ΨK(2,λ))]=

xh(Pm-1)hr(Pm+1)h(ΨK(2，λ))+

xh(Pm-1)hr(Pm+1)h(ΨK(2,λ))]=

2xh(Pm-1)hr(Pm+1)h(ΨK(2,λ))]

設k是任意自然數，q是奇數，2≤r∈N,δ=(r+1)m+r，我們引入圖的頂點記號

λk=(2kq-1)+2k-1qδ,容易推知λ1=(2q-1)+qδ，λk=2λk-1+1(k≥2)

設n是形如n=2k-1q-1的奇數，注意到λk=(2kq-1)+2k-1qδ，則計算可得

2λ+1=(2n+1)+(n+1)δ=(2kq-1)+2k-1qδ=λk

(19)

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

(20)

4 因式分解定理

定理4.1設r(≥1)是任意自然數，m∈N,m≥3，，δ=(r+1)m+r，則有

(21)

(22)

證明對于?r∈N,r≥1,m≥3，注意到h(K1)=x，由引理2.5、(13)和(6)兩式，即得

xr+1[h(Pm)+(r+1)h(Pm-1)]=

h(Pm)hr-1(Pm+1)h(Ψ(r+1),m)

即(21)式成立；根據(21)式及引理2.5，容易推知(22)成立。

定理4.2設n(≥3)為奇數，r≥1，δ=(r+1)m+r，λ=n+2-1(n+1)δ,則有

(23)

(24)

證明(ⅰ)若n(≥3)為奇數時，注意到δ=(r+1)m+r，λk=(2kq-1)+2k-1qδ，由引理2.5、(17)和(14)兩式，即得

x2h(ΨK(2,λ))[h(ΨK(2,λ))+

這里λ=n+2-1(n+1)δ，λ-2-δ=(n-2)+2-1(n-1)δ,故(23)式成立。

(ⅱ)根據引理2.4及(23)式，立即推知(24)式也成立。

把(19)和(20)兩式依次代入(23)和(24)兩式，我們有如下的

定理4.3設?k∈N，q是奇數，r≥1，λk=(2kq-1)+2k-1qδ,則有

(25)

(26)

定理4.4設?k∈N,q(≥3)是奇數，λk=(2kq-1)+2k-1qδ，δ=(r+1)m+r，則有

(27)

(28)

證明(ⅰ)對自然數k≥2作數學歸納法：當k=2時，由(25)式易推知

此時(35)式成立：假定結論對于k-1成立，對于k的情形，由引理2.5、(25)式及歸納假定即得

由此可知當k時結論也成立，故由數學歸納法原理知，對于任意的自然數k≥2，(27)式成立；

(ⅱ)根據引理2.4及(27)式，立即推知(28)式也成立。

定理4.5設n(≥3)為奇數，r≥1，δ=(r+1)m+r，λ=n+2-1(n+1)δ,則有

(29)

ΨT(2δ,(λ+1)+2))

(30)

證明(ⅰ)若n(≥3)為奇數時，注意到δ=(r+1)m+r，λ=n+2-1(n+1)δ，由引理2.5、(18)和(16)兩式，即得

2xh(Pm-1)hr(Pm+1)h(ΨK(2,λ))]=

這里δ=(r+1)m+r，λ+1=(n+1)+2-1(n+1)δ,故(29)式成立;

(ⅱ)根據引理2.4及(29)式，立即推知(30)式也成立。

定理4.6設n(≥3)為奇數，r≥1，δ=(r+1)m+r，λ=n+2-1(n+1)δ,則有

h(Pm)hr-1(Pm+1)h(Ψ(r+1),

(31)

(32)

證明(ⅰ)若n(≥3)為奇數時，注意到δ=(r+1)m+r，λ=n+2-1(n+1)δ，以及λ+1=(n+1)+2-1(n+1)δ，由引理2.5、(29)和(21)兩式，即得

故(31)式成立;

(ⅱ)根據引理2.4及(31)式，立即推知(32)式也成立。

5 圖的色價性分析

在給出幾類圖的伴隨分解的基礎上，我們來討論這些圖色等價性。

證明根據(28)式知

定理5.2設n(≥3)為奇數，r≥1，δ=(r+1)m+r，λ=n+2-1(n+1)δ,則圖簇

證明根據(24)式知

仿此，根據定義2.2和引理2.2以及(26)、(28)、(30)、(32)等四個公式，同法可證如下的幾個結論：

定理5.5設n(≥3)為奇數，r≥1，δ=(r+1)m+r，λ=n+2-1(n+1)δ,則圖簇

定理5.6設n(≥3)為奇數，r≥1，δ=(r+1)m+r，λ=n+2-1(n+1)δ,