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

寶 音，張秉儒

(1.青海民族大學(xué) 蒙學(xué)系，青海 西寧 810007；2.青海師范大學(xué) 數(shù)學(xué)系，青海 西寧 810008)

?

·數(shù)理科學(xué)·

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

寶 音1，張秉儒2

(1.青海民族大學(xué) 蒙學(xué)系，青海 西寧 810007；2.青海師范大學(xué) 數(shù)學(xué)系，青海 西寧 810008)

伴隨多項(xiàng)式;因式分解;色等價(jià)性

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

代數(shù)圖論是從圖的組合結(jié)構(gòu)出發(fā)研究其代數(shù)性質(zhì),用代數(shù)指標(biāo)反映圖的組合構(gòu)信息人們?cè)噲D研究其圖多項(xiàng)式逆問(wèn)題,即利用圖多項(xiàng)式本身所蘊(yùn)涵的圖論組合意義,刻畫(huà)色多項(xiàng)式所確定的圖和一些圖的色等價(jià)類(lèi),用伴隨多項(xiàng)式理論研究色唯一圖和色等價(jià)圖,找到了許多色唯一圖和刻畫(huà)了許多色等價(jià)圖,最新成果包含在Koh，Dong和Teo完成的專(zhuān)著《Chromaticity and Chromatic Polynomials of Graphs 》中。本文的主要目的是運(yùn)用圖的伴隨多項(xiàng)式的性質(zhì),討論圖的伴隨多項(xiàng)式的因式分解的圖論方法，以研究一個(gè)圖的補(bǔ)圖的色等價(jià)圖的新方法。

設(shè)p(G,λ)為圖G的色多項(xiàng)式,稱(chēng)圖G與H色等價(jià),若P(G,λ)=P(H,λ);稱(chēng)圖G是色唯一圖,若從P(H,λ)=P(G,λ)得到圖H與G同構(gòu),記為G?H.Chao和Whitehead于1978年首先提出色等價(jià)圖和色唯一圖的概念[3-4]。1987年劉儒英提出了圖G的伴隨多項(xiàng)式h(G,x)和伴隨唯一性的概念[5],并在色唯一圖的研究中獲得一系列新成果[6-8]。目前色等價(jià)圖的結(jié)構(gòu)規(guī)律尚待解決。

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

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

(1)

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

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

(2)

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

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

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

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

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

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

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

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

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

根據(jù)引理4，容易推知如下的引理。

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

h(H)h(nG)=h(H)hn(G);

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

引理6[10]設(shè)n≥2是自然數(shù),Sn+1表示具有n個(gè)頂點(diǎn)的星圖,則有

(i)h(Sn+1)=xh(Sn)+xn;

(ii)h(Sn+1)=xn+1+nxn。

引理7[11]設(shè)m,k∈N,k≥m≥2,則有h(Ψ(k,m))=xk[h(Pm)+kh(Pm-1)]。

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

圖1 圖ΨK(k,m+2-1(m+1)r),m=2t+1Fig.1 ΨK(k,m+2-1(m+1)r),m=2t+1

圖2 圖Ψ*(2,2,m+2-1(m+1)r),m=2t+1Fig.2 Ψ*(2,2,m+2-1(m+1)r),m=2t+1

圖3 圖ΨT(r,2,m+2-1mr),m=2tFig.3 ΨT(r,2,m+2-1mr),m=2t

引理8 設(shè)k≥1是任意的自然數(shù),m是奇數(shù),m≥r≥3,則有

(i)h(ΨK(1,m+2-1(m+1)r))=

xrh(ΨK(1,(m-2)+2-1(m-1)r))]，

(3)

(ii)h(ΨK(2,m+2-1(m+1)r))=

2xrh(ΨK(1,(m-2)+2-1(m-1)r))]，

(4)

(iii)h(ΨK(k,m+2-1(m+1)r))=

kxrh(ΨK(1,(m-2)+2-1(m-1)r))]。

(5)

證 明 如圖1所示,在圖ΨK(1,m+2-1(m+1)r)和ΨK(2,m+2-1(m+1)r)中均取邊e=u1v1,則由引理3和引理4,依次得到以下兩個(gè)公式

h(ΨK(1,m+2-1(m+1)r))=

xr+1h(ΨK(1,(m-2)+2-1(m-1)r))，

h(ΨK(2,m+2-1(m+1)r))=

xh(ΨK(2,m+2-1(m+1)r))+

xr+2h(ΨK(1,(m-2)+2-1(m-1)r))。

由上面的兩式立即得到式(3)和(4)。

如圖1所示,在圖ΨK(k,m+2-1(m+1)r)中取邊e=u1v1,由引理3和引理4,即得

h(ΨK(k,m+2-1(m+1)r))=

xh(ΨK(k-1,m+2-1(m+1)r))+

xr+kh(ΨK(1,(m-2)+2-1(m-1)r))。

(6)

下證式(5)成立,對(duì)頂點(diǎn)數(shù)k作數(shù)學(xué)歸納法,當(dāng)k=1,2時(shí),由式(3)和(4)可知,此時(shí)公式成立;假定公式對(duì)k-1(k≥3)的情形成立,即

h(ΨK(k-1,m+2-1(m+1)r))=

(k-1)xrh(ΨK(1,(m-2)+

2-1(m-1)r))]，

則對(duì)于k的情形,根據(jù)式(6)及歸納假定，有

h(ΨK(k,m+2-1(m+1)r))=

xh(ΨK(k-1,m+2-1(m+1)r))+

xr+kh(ΨK(1,(m-2)+

2-1(m-1)r))=

(k-1)xrh(ΨK(1,(m-2)+

2-1(m-1)r))]+

xr+kh(ΨK(1,(m-2)+2-1(m-1)r))=

kxrh(ΨK(1,(m-2)+2-1(m-1)r))]，

即當(dāng)k時(shí)公式也成立,由數(shù)學(xué)歸納法原理可知,對(duì)任意的自然數(shù)k,式(5)成立。

引理9 設(shè)m為奇數(shù),r是自然數(shù),m>r≥3,則有

(i)h(Ψ*(1,2,m+2-1(m+1)r))=

x[h(ΨK(2,m+2-1(m+1)r))+

xrh(Ψ*(1,2,(m-2)+2-1(m-1)r))]，

(7)

(ii)h(Ψ*(2,2,m+2-1(m+1)r))=

x2[h(ΨK(2,m+2-1(m+1)r))+

2xrh(Ψ*(1,2,(m-2)+2-1(m-1)r))]。

(8)

證 明 (i) 如圖2所示,m為奇數(shù),此時(shí)刪除1度點(diǎn)T1,T2,U1,U2以外,其余的頂點(diǎn)數(shù)為m+2-1(m+1)r,在圖Ψ*(1,2,m+2-1(m+1)r)中取邊e=T1Vm,由引理3和引理4,得到

h(Ψ*(1,2,m+2-1(m+1)r)) =

xh(ΨK(2,m+2-1(m+1)r))+

xr+1h(Ψ*(1,2,(m-2)+2-1(m-1)r))，

由此可知式(7)成立;

(ii) 在圖Ψ*(2,2,m+2-1(m+1)r)中取邊e=T1Vm,同理可得

h(Ψ*(2,2,m+2-1(m+1)r))=

xh(Ψ*(1,2,m+2-1(m+1)r))+

xr+2h(Ψ*(1,2,(m-2)+2-1(m-1)r))，

由此及式(7)可推知式(8)成立。

引理10 設(shè)m為偶數(shù),r是自然數(shù),m>r≥3,則有

h(ΨK(2,(m+1)+2-1(m+2)r))=

h(Sr+1)h(Ψ*(1,2,(m-1)+2-1mr))+

xr+1h(ΨK(2,(m-1)+2-1mr))。

(9)

證 明 參考圖1,m是偶數(shù),則m+1是奇數(shù),故d(vm)=2,d(vm+1)=r+1,在圖ΨK(2,(m+1)+2-1(m+2)r)中取邊e=vmvm+1,則由引理3和引理4,即得式(9)。

引理11 設(shè)m為偶數(shù)時(shí),r∈N,m≥r≥3,則有

(i)h(ΨT(r,2,m+2-1mr))=

h(ΨK(2,(m+1)+2-1(m+2)r))=

h(Sr+1)h(Ψ*(1,2,(m-1)+2-1mr))+

xr+1h(ΨK(2,(m-1)+2-1mr))，

(10)

(ii)h(ΨT(2r,2,m+2-1mr))=

h(Sr+1)[h(Sr+1)h(Ψ*(1,2,(m-1)+2-1mr))+

2xr+1h(ΨK(2,(m-1)+2-1mr))]。

(11)

證 明 (i) 當(dāng)m為偶數(shù)時(shí),如圖3所示,圖ΨT(r,2,m+2-1(m+1)r)即為ΨK(2,(m+1)+2-1(m+2)r),故由式(9)即得式(10);

(ii)當(dāng)m為偶數(shù)時(shí),此時(shí)m-1為偶數(shù),d(u1)=r+1,d(Vm)=3,如圖3所示,在圖ΨΤ(2r,2,m+2-1mr)中取e=u1Vm,由引理3和引理4,并運(yùn)用式(10),即得

h(ΨT(2r,2,m+2-1(m+1)r))=

h(Sr+1)h(ΨT(r,2,m+2-1mr))+

xr+1h(Sr+1)h(ΨK(2,(m-1)+2-1mr))=

h(Sr+1)[h(ΨT(r,2,m+2-1mr))+

xr+1h(ΨK(2,(m-1)+2-1mr))]=

h(Sr+1)[h(Sr+1)h(ΨK(1,(m-1)+

2-1mr))+xr+1h(ΨK(2,(m-1)+2-1mr))+

xr+1h(ΨK(2,(m-1)+2-1mr))]=

h(Sr+1)[h(Sr+1)h(Ψ*(1,2,(m-1)+

2-1mr))+2xr+1h(ΨK(2,(m-1)+

2-1mr))]。

由此可知式(11)成立。

4 兩類(lèi)圖的伴隨多項(xiàng)式的因式分解

4.1 兩類(lèi)圖的伴隨多項(xiàng)式

圖4 圖Ψ*(2,2,(2m+1)+(m+1)r),m=2t+1Fig.4 Ψ*(2,2,(2m+1)+(m+1)r),m=2t+1

圖5 圖Ψ*(2,2,(2m+1)+mr), m=2tFig.5 Ψ*(2,2,(2m+1)+mr), m=2t

引理12 設(shè)m,r是自然數(shù),m>r≥3,則有

(i) 若m為奇數(shù),

h(Ψ*(2,2,(2m+1)+(m+1)r))=

h(ΨK(2,m+2-1(m+1)r))

[xh(ΨK(2,m+2-1(m+1)r))+

2xr+1h(Ψ*(1,2,(m-2)+2-1(m-1)r))]

(12)

(ii) 若m為偶數(shù),

h(Ψ*(2,2,(2m+1)+mr))=

h(Ψ*(1,2,(m-1)+2-1mr))

[h(Sr+1)h(Ψ*(1,2,(m-1)+2-1mr))+

2xr+1h(ΨK(2,(m-1)+2-1mr))]

(13)

證 明 (i) 如圖4所示,因?yàn)閙是奇數(shù),故d(Vm)=r+2,d(Vm+1)=2,在圖Ψ*(2,2,(2m+1)+(m+1)r)中取邊e=VmVm+1,則由引理3、引理4，有

h(Ψ*(2,2,(2m+1)+(m+1)r))=

h(ΨK(2,m+2-1(m+1)r))

h(Ψ*(1,2,m+2-1(m+1)r))+

xr+1h(Ψ*(1,2,(m-2)+

2-1(m-1)r))h(ΨK(2,m+2-1(m+1)r))=

h(ΨK(2,m+2-1(m+1)r))

[h(Ψ*(1,2,m+2-1(m+1)r))+

xr+1h(Ψ*(1,2,(m-2)+2-1(m-1)r))]，

把式(7)代入上式,即得

h(Ψ*(2,2,(2m+1)+(m+1)r))=

h(ΨK(k,m+2-1(m+1)r))

[xh(ΨK(2,m+2-1(m+1)r))+

2xr+1h(Ψ*(1,2,(m-2)+2-1(m-1)r))]，

由此可知式(12)成立;

(ii) 如圖5所示,因?yàn)閙是偶數(shù),故d(Vm)=2,d(Vm+1)=r+2,在圖Ψ*(2,2,(2m+1)+mr)中取邊e=VmVm+1,則由引理3和引理4,有

h(Ψ*(2,2,(2m+1)+mr))=

h(Ψ*(1,2,(m-1)+

2-1mr))h(ΨK(2,(m+1)+

2-1(m+2)r))+

xr+1h(ΨK(2,(m-1)+

2-1mr))h(Ψ*(1,2,(m-1)+2-1mr))=

h(Ψ*(1,2,(m-1)+2-1mr))·

[h(ΨK(2,(m+1)+2-1(m+2)r))+

xr+1h(ΨK(2,(m-1)+2-1mr))]，

把式(9)代入上式,即得

h(Ψ*(2,2,(2m+1)+mr))=

h(Ψ*(1,2,(m-1)+

2-1mr))[h(Sr+1)h(Ψ*(1,2,(m-1)+

2-1mr))+

2xr+1h(ΨK(2,(m-1)+2-1mr))]，

因此式(13)成立。

4.2 因式分解定理

定理1 設(shè)m是奇數(shù),r是自然數(shù),m>r≥3,則有

(i)h(Ψ*(2,2,(2m+1)+

(m+1)r)∪K1)=

h(ΨK(2,m+2-1(m+1)r))·

h(Ψ*(2,2,m+2-1(m+1)r))，

(14)

(ii)h(Ψ*(2,2,(2m+1)+

(m+1)r)∪K1)=

h(ΨK(2,m+2-1(m+1)r)

∪Ψ*(2,2,m+2-1(m+1)r))。

(15)

證 明

(i) 若m是奇數(shù), 由引理5,并根據(jù)(12)和(8)兩式,即得

h(Ψ*(2,2,(2m+1)+(m+1)r)∪K1)=

xh(Ψ*(2,2,(2m+1)+(m+1)r))=

xh(ΨK(2,m+2-1(m+1)r))·

[xh(ΨK(2,m+2-1(m+1)r))+

2xr+1h(Ψ*(1,2,(m-2)+

2-1(m-1)r))]=

h(ΨK(2,m+2-1(m+1)r))·

x2[h(ΨK(2,m+2-1(m+1)r))+

2xrh(Ψ*(1,2,(m-2)+

2-1(m-1)r))]=

h(ΨK(2,m+2-1(m+1)r))

h(Ψ*(2,2,m+2-1(m+1)r))

所以式(14)成立;

(ii) 根據(jù)式(14)及引理4,容易推知式(15)成立。

定理2 設(shè)m是偶數(shù),r是自然數(shù),m>r≥3,則有

(i)h(Ψ*(2,2,(2m+1)+

mr)∪Sr+1)=

h(Ψ*(1,2,(m-1)+

2-1mr))h(ΨT(2r,2,m+2-1mr))

(16)

(ii)h(Ψ*(2,2,(2m+1)+mr)∪Sr+1)=

h(Ψ*(1,2,(m-1)+2-1mr)∪

ΨT(2r,2,m+2=1mr))

(17)

證 明 (i) 若m是偶數(shù),由引理5,并根據(jù)(13)和(11)兩式,即得

h(Ψ*(2,2,(2m+1)+mr)∪Sr+1)=

h(Sr+1)h(Ψ*(2,2,(2m+1)+mr))=

h(Sr+1)h(Ψ*(1,2,(m-1)+2-1mr))·

[h(Sr+1)h(Ψ*(1,2,(m-1)+2-1mr))+

2xr+1h(ΨK(2,(m-1)+2-1mr))]=

h(ΨK(1,k,(m-1)+2-1mr))·

h(ΨT(2r,k,m+2-1mr))

所以式(16)也成立。

(ii) 根據(jù)引理4及式(16)可知,(17)也成立,由此可知(16)與(17)兩式是等價(jià)的。

若m是形如m=2nq-1的奇數(shù),令λn=(2nq-1)+2n-1qr,?n∈N,則有

(2m+1)+(m+1)r=

(2n+1q-1)+2nqr=λn+1，

于是由式(14),即得以下推論。

推論1 設(shè)m=2nq-1,q是奇數(shù),q≥r≥3,λn=(2nq-1)+2n-1qr,則有

h(Ψ*(2,2,λn+1)∪K1)=

h(Ψ*(2,2,λn))h(ΨK(2,λn))

(18)

在式(18)中令n=1,2,3，有如下的推論。

推論2 設(shè)m=2nq-1,q是奇數(shù),q≥r≥3,λn=(2nq-1)+2n-1qr,則有

(i)h(Ψ*(2,2,λ2)∪K1)=

h(Ψ*(2,2,λ1))h(ΨK(2,λ1))，

(19)

(ii)h(Ψ*(2,2,λ3)∪K1)=

h(Ψ*(2,2,λ2))h(ΨK(2,λ2))，

(20)

(iii)h(Ψ*(2,2,λ4)∪K1)=

h(Ψ*(2,2,λ3))h(ΨΚ(2,λ3))。

(21)

推論3 設(shè)m=2nq-1,q是奇數(shù),q≥r≥3,λn=(2nq-1)+2n-1qr,則有

(i)h(Ψ*(2,2,λ3)∪2K1)=

h(Ψ*(2,2,λ1))h(ΨK(2,λ1))·

h(ΨK(2,λ2))，

(22)

(ii)h(Ψ*(2,2,λ4)∪3K1)=

h(Ψ*(2,2,λ1))h(ΨK(2,λ1))h(ΨK(2,λ2))·

h(ΨK(2,λ3)) 。

(23)

證 明 (i) 由引理5,并根據(jù)(20)和(19)兩式,即得

h(Ψ*(2,2,λ3)∪2K1)=

xh(Ψ*(2,2,λ3)∪K1)=

xh(Ψ*(2,2,λ2))h(ΨK(2,λ2))=

h(Ψ*(2,2,λ2)∪K1)h(ΨK(2,λ2))=

h(Ψ*(2,2,λ1))h(ΨK(2,λ1))h(ΨK(2,λ2))，故式(22)成立;

(ii) 由引理5,并根據(jù)(21)和(22)兩式,即得

h(Ψ*(2,2,λ4)∪3K1)=

x2h(Ψ*(2,2,λ4)∪K1)=

x2h(Ψ*(2,2,λ3))h(ΨK(2,λ3))=

h(Ψ*(2,2,λ3)∪2K1)h(ΨK(2,λ3))=

h(Ψ*(2,2,λ1))·

h(ΨK(2,λ1))h(ΨK(2,λ2))h(ΨK(2,λ3))，

故式(23)也成立。

定理3 設(shè)m=2nq-1,q是奇數(shù),q≥r≥3,λn=(2nq-1)+2n-1qr,則有

(i)h(Ψ*(2,2,λn+1)∪nK1)=

h(Ψ*(2,2,λ1))h(ΨK(2,λ1))h(ΨK(2,λ2))…

h(ΨK(2,λn-1))h(ΨK(2,λn))，

(24)

(ii)h(Ψ*(2,2,λn+1)∪nK1)=

h(Ψ*(2,2,λ1)∪ΨK(2,λ1)∪ΨK(2,λ2)∪…

∪ΨK(2,λn-1)∪ΨK(2,λn))。

(25)

證 明 (i) 對(duì)個(gè)數(shù)n≥2作數(shù)學(xué)歸納法。當(dāng)n=2,3,4時(shí),由(19)、(22)和(23)三式可知結(jié)論成立;假定結(jié)論對(duì)于n-1的情形成立,則對(duì)于n的情形,由引理5,并根據(jù)(18)和歸納假定,有

h(Ψ*(2,2,λn+1)∪nK1)=

xn-1h(Ψ*(2,2,λn+1)∪K1)=

xn-1h(Ψ*(2,2,λn))h(ΨK(2,λn))=

h(Ψ*(2,2,λn)∪(n-1)K1)h(ΨK(2,λn))=

h(Ψ*(2,2,λ1))h(ΨK(2,λ1))·

h(ΨK(2,λ2))…h(huán)(ΨK(2,λn-1))h(ΨK(2,λn))

即當(dāng)n時(shí)結(jié)論也成立,根據(jù)數(shù)學(xué)歸納法原理可知,對(duì)于任意的自然數(shù)n≥2,結(jié)論都成立。

(ii) 根據(jù)式(24)及引理4,容易推知式(25)成立。

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

在給出幾類(lèi)圖的伴隨分解的基礎(chǔ)上,來(lái)討論這些圖色等價(jià)性。

定理4 設(shè)m是奇數(shù),r是自然數(shù),m>r≥3,則圖簇Ψ*(2,2,(2m+1)+(m+1)r)與ΨK(2,m+2-1(m+1)r)∪Ψ*(2,2,m+2-1(m+1)r) 二者的補(bǔ)圖是色等價(jià)的。

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

h(Ψ*(2,2,(2m+1)+

(m+1)r)∪K1)=

h(ΨK(2,m+2-1(m+1)r)∪

Ψ*(2,2,m+2-1(m+1)r))

由此及定義2可知,圖簇ΨK(2,m+2-1(m+1)r)∪Ψ*(2,2,m+2-1(m+1)r) 與Ψ*(2,2,(2m+1)+(m+1)r)二者是伴隨等價(jià)的,由此及引理2,它們的補(bǔ)圖是色等價(jià)的。

定理5 設(shè)m是偶數(shù),r是自然數(shù),m>r≥3,則圖簇Ψ*(k,k,(2m+1)+mr)∪Sr+1與Ψ*(1,2,(m-1)+2-1mr)∪ΨT(2r,2,m+2-1mr) 二者的補(bǔ)圖是色等價(jià)的。

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

h(Ψ*(2,2,(2m+1)+mr)∪Sr+1)=

h(Ψ*(1,2,(m-1)+2-1mr)∪

ΨT(2r,2,m+2-1mr))

由此及定義2可知,圖簇Ψ*(1,2,(m-1)+2-1mr)∪ΨT(2r,2,m+2-1mr) 與Ψ*(k,k,(2m+1)+mr)∪Sr+1二者是伴隨等價(jià)的,由此及引理2,它們的補(bǔ)圖是色等價(jià)的。

由式(18)得到

h(Ψ*(2,2,λn+1)∪K1)=

h(Ψ*(2,2,λn)∪ΨK(2,λn))。

(26)

仿照定理4及定理5的證明,由式(26)和式(25),即可證明如下定理。

定理6 設(shè)?n∈N,n≥2,且q是奇數(shù),q≥r≥3,λn=(2nq-1)+2n-1qr,則兩個(gè)圖簇Ψ*(2,2,λn+1)∪K1與Ψ*(2,2,λn)∪ΨK(2,λn)的補(bǔ)圖是色等價(jià)圖。

定理7 設(shè)?n∈N,n≥2,且q是奇數(shù),q≥r≥3,λn=(2nq-1)+2n-1qr,則圖簇Ψ*(2,2,λn+1)∪nK1與Ψ*(2,2,λ1)∪ΨK(2,λ1)∪ΨK(2,λ2)∪…∪ΨK(2,λn-1)∪ΨK(2,λn)的補(bǔ)圖是色等價(jià)圖。

[1]BODYJA,MURTYUSR.GraphTheorywithApplications[M].Amsterdam:North-Holland, 1976.

[2]BOLLOBASB.ModernGraphTheory[M].NewYork:Spinger-Verlag，1998.

[3]CHAOCY,WHITEHEADEG.Onchromaticequivalenceofgraph[J].SpringerLectureNoteinMathematics,1978，642：121-131.

[4]KOHKM,TEOKL.Thesearchforchromaticallyuniquegraphs[J].GraphCombin，1990(6):259-285.

[5]BIGGSN.AlgebraicGraphTheory[M].Cambridge:CambridgeUniversityPress, 1974.

[8]ZHAOHX,LIXL,LIURY.Onproblemsandconjecturesonadjointlyequivalentgraphs[J].DiscreteMathematics, 2005,295:203-212.

[9] 劉儒英.關(guān)于兩類(lèi)圖的色多項(xiàng)式[J]. 科學(xué)通報(bào), 1987(3):236.

[10] 張秉儒. 圖的伴隨多項(xiàng)式的兩個(gè)因式分解定理及其應(yīng)用[J]. 數(shù)學(xué)研究與評(píng)論, 2003,23(2):355-361.

[11] 郭玉琳,張秉儒.若干圖簇的伴隨多項(xiàng)式的因式分解及色性分析[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2005, 35(9):167-172.

(編 輯亢小玉)

The factorizations of adjoint polynomials of a kind of graphs and chromatically equivaleness of their complements

BAO Yin1， ZHANG Bing-ru2

(1.Department of Mongol, Qinghai National University, Xining 810007, China; 2.Department of Mathematics, Qinghai Normal University, Xining 810008, China)

adjoint polynomials; factorization; chromatically equivalence

2014-04-13

國(guó)家自然科學(xué)基金資助項(xiàng)目(10861009;10761008);青海省自然科學(xué)基金資助項(xiàng)目(2011-Z-911)

寶音，男，內(nèi)蒙古赤峰人，教授，從事圖論和組合數(shù)學(xué)研究。

O157.5

：ADOI：10.16152/j.cnki.xdxbzr.2015-03-001