一類樹的伴隨多項(xiàng)式的分解及其補(bǔ)圖的色等價(jià)性

熊鵬飛，張秉儒

(1.青海交通職業(yè)技術(shù)學(xué)院，青海 西寧 810006；2.青海師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，青海 西寧 810008)

1 預(yù)備知識(shí)

2 圖的伴隨多項(xiàng)式的概念

設(shè)G是p的階圖,若圖G的生成子圖G0的所有分支是完全圖，則稱G0為G圖的理想子圖。用bi(G)表示圖G的具有p-i個(gè)分支的理想子圖的個(gè)數(shù)(0≤i≤p-1),由文[4]的定理15可知

(1)

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

定義2.1[5]設(shè)G是p階圖，則圖G的多項(xiàng)式

(2)

稱為簡(jiǎn)單圖G的伴隨多項(xiàng)式，h(G,x)可以簡(jiǎn)記為h(G)。

圖G的每個(gè)分支或是K1或是K2的生成子圖稱為圖G的一個(gè)匹配，圖G的一個(gè)k-匹配就是含有k條邊的匹配，由G的理想子圖的個(gè)數(shù)bi(G)的定義即得如下的

引理2.1[5]若G是無三角形K3的圖，則bi(G)等于圖G的i-匹配的數(shù)目。

定義2.2稱圖G與H是伴隨等價(jià)的，若h(G,x)=h(H,x)；稱圖G是伴隨唯一的，若從h(H,x)=h(G,x)推出圖G與H同構(gòu)，記為H≌G。

我們常用到圖的伴隨多項(xiàng)式h(G,x)的如下的基本性質(zhì)：

引理2.3[7]設(shè)uv∈E(G)且uv不屬于圖G的任何三角形，則有

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

引理2.4[7]設(shè)圖G具有k個(gè)分支G1,G2,…,Gk，則有

設(shè)G是任意的連通圖，其伴隨多項(xiàng)式h(G,x)以下簡(jiǎn)記為h(G)。并不再贅述。

根據(jù)引理2.4,我們?nèi)菀淄浦缦碌?/p>

引理2.5設(shè)G和H是任意的兩個(gè)圖，K1是一個(gè)孤立點(diǎn)，n≥2是任意的自然數(shù)，則有

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

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

引理2.6[9-10]設(shè)n≥2是自然數(shù)，Pn表示具有n個(gè)頂點(diǎ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]設(shè)?k∈N,m(≥3)是自然數(shù)，Ψ(k,m)表示把星圖Sk+1的唯一k度點(diǎn)與Pm的一個(gè)1度點(diǎn)重迭后得到的圖,則有

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

(5)

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

(6)

3 幾類新圖的伴隨多項(xiàng)式

引理3.1設(shè)m(≥3)是任意自然數(shù)，?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設(shè)m(≥3)是任意自然數(shù)，?r∈N,r≥1，δ=(r+1)m+r，則有

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

(9)

證明如圖3.1所示,對(duì)自然數(shù)r≥1作數(shù)學(xué)歸納法：當(dāng)r=1,2時(shí)，由(7)和(8)兩式知公式成立；假定公式對(duì)r-1成立，即

根據(jù)(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)]

由數(shù)學(xué)歸納法原理知，公式(9)對(duì)于任意自然數(shù)r都成立。

我們定義頂點(diǎn)數(shù)記號(hào):λ=(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設(shè)n(≥4)是偶數(shù)，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設(shè)n(≥4)為偶數(shù)，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設(shè)r(≥1)是任意自然數(shù)，m∈N,m≥3，δ=(r+1)m+r，則有

(14)

(15)

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

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

定理4.2設(shè)n(≥4)為偶數(shù)，r≥1，δ=(r+1)m+r，λ=(n+1)+2-1(n+2)δ,則有

(16)

(17)

證明(ⅰ)若n(≥4)為偶數(shù)時(shí)，注意到δ=(r+1)m+r，λ=(n+1)+2-1(n+2)δ，由引理2.5、(11)和(16)兩式，即得

故(16)式成立；

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

定理4.3設(shè)n(≥4)為偶數(shù)，r≥1，δ=(r+1)m+r，λ=(n+1)+2-1(n+2)δ,則有

(18)

(19)

證明(ⅰ)根據(jù)引理2.5、(14)和(16)兩式，即得

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

5 圖的色價(jià)性分析

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

證明根據(jù)(15)式知

證明根據(jù)(17)式知

仿此，根據(jù)定義2.2和引理2.2以及(19)式，同法可證如下的結(jié)論：