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

寶 音，張秉儒

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

?

·數理科學·

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

寶 音1，張秉儒2

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

伴隨多項式;因式分解;色等價性

1 預備知識

代數圖論是從圖的組合結構出發研究其代數性質,用代數指標反映圖的組合構信息人們試圖研究其圖多項式逆問題,即利用圖多項式本身所蘊涵的圖論組合意義,刻畫色多項式所確定的圖和一些圖的色等價類,用伴隨多項式理論研究色唯一圖和色等價圖,找到了許多色唯一圖和刻畫了許多色等價圖,最新成果包含在Koh，Dong和Teo完成的專著《Chromaticity and Chromatic Polynomials of Graphs 》中。本文的主要目的是運用圖的伴隨多項式的性質,討論圖的伴隨多項式的因式分解的圖論方法，以研究一個圖的補圖的色等價圖的新方法。

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

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)。

定義1[5]設G是p階圖,則圖G的多項式

(2)

稱為簡單圖G的伴隨多項式,h(G,x)可以簡記為h(G)。

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

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

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

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

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

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

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

設G是任意的連通圖,其伴隨多項式h(G,x)以下簡記為h(G)。不再贅述。

根據引理4，容易推知如下的引理。

引理5 設G和H是任意的兩個圖,K1是一個孤立點,n≥2是任意的自然數,則有

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

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

引理6[10]設n≥2是自然數,Sn+1表示具有n個頂點的星圖,則有

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

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

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

3 幾類新圖的伴隨多項式

圖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 設k≥1是任意的自然數,m是奇數,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,依次得到以下兩個公式

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)成立,對頂點數k作數學歸納法,當k=1,2時,由式(3)和(4)可知,此時公式成立;假定公式對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))]，

則對于k的情形,根據式(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))]，

即當k時公式也成立,由數學歸納法原理可知,對任意的自然數k,式(5)成立。

引理9 設m為奇數,r是自然數,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為奇數,此時刪除1度點T1,T2,U1,U2以外,其余的頂點數為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 設m為偶數,r是自然數,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是偶數,則m+1是奇數,故d(vm)=2,d(vm+1)=r+1,在圖ΨK(2,(m+1)+2-1(m+2)r)中取邊e=vmvm+1,則由引理3和引理4,即得式(9)。

引理11 設m為偶數時,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) 當m為偶數時,如圖3所示,圖ΨT(r,2,m+2-1(m+1)r)即為ΨK(2,(m+1)+2-1(m+2)r),故由式(9)即得式(10);

(ii)當m為偶數時,此時m-1為偶數,d(u1)=r+1,d(Vm)=3,如圖3所示,在圖ΨΤ(2r,2,m+2-1mr)中取e=u1Vm,由引理3和引理4,并運用式(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 兩類圖的伴隨多項式的因式分解

4.1 兩類圖的伴隨多項式

圖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 設m,r是自然數,m>r≥3,則有

(i) 若m為奇數,

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為偶數,

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所示,因為m是奇數,故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所示,因為m是偶數,故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 設m是奇數,r是自然數,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是奇數, 由引理5,并根據(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) 根據式(14)及引理4,容易推知式(15)成立。

定理2 設m是偶數,r是自然數,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是偶數,由引理5,并根據(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) 根據引理4及式(16)可知,(17)也成立,由此可知(16)與(17)兩式是等價的。

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

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

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

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

推論1 設m=2nq-1,q是奇數,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 設m=2nq-1,q是奇數,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 設m=2nq-1,q是奇數,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,并根據(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,并根據(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 設m=2nq-1,q是奇數,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) 對個數n≥2作數學歸納法。當n=2,3,4時,由(19)、(22)和(23)三式可知結論成立;假定結論對于n-1的情形成立,則對于n的情形,由引理5,并根據(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(ΨK(2,λn-1))h(ΨK(2,λn))

即當n時結論也成立,根據數學歸納法原理可知,對于任意的自然數n≥2,結論都成立。

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

5 圖的色價性分析

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

定理4 設m是奇數,r是自然數,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) 二者的補圖是色等價的。

證 明 根據式(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)二者是伴隨等價的,由此及引理2,它們的補圖是色等價的。

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

證 明 根據式(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二者是伴隨等價的,由此及引理2,它們的補圖是色等價的。

由式(18)得到

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

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

(26)

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

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

定理7 設?n∈N,n≥2,且q是奇數,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)的補圖是色等價圖。

[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] 劉儒英.關于兩類圖的色多項式[J]. 科學通報, 1987(3):236.

[10] 張秉儒. 圖的伴隨多項式的兩個因式分解定理及其應用[J]. 數學研究與評論, 2003,23(2):355-361.

[11] 郭玉琳,張秉儒.若干圖簇的伴隨多項式的因式分解及色性分析[J].數學的實踐與認識, 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

國家自然科學基金資助項目(10861009;10761008);青海省自然科學基金資助項目(2011-Z-911)

寶音，男，內蒙古赤峰人，教授，從事圖論和組合數學研究。

O157.5

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