零強(qiáng)迫數(shù)為最大度的樹圖

涂東鑫,陳鴻章

（閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,福建漳州 363000）

考慮的圖為簡單圖.設(shè)圖G為n階簡單圖,其頂點(diǎn)集和邊集分別為V(G),E(G).對任意v∈V(G),用dG(v)和N(v)分別表示頂點(diǎn)v的度和鄰域；用δ(G)和Δ(G)分別表示圖G的最小度和最大度.圖G中度數(shù)為1的點(diǎn)稱為懸掛點(diǎn),用p(G)表示圖G中懸掛點(diǎn)的數(shù)目.稱v∈V(G)是圖G的一個(gè)割點(diǎn)當(dāng)且僅當(dāng)ο(Gv)＞ο(G),其中ο(G)表示G中連通分支的數(shù)目；稱e∈E(G)是圖G的一條割邊當(dāng)且僅當(dāng)ο(Ge)＞ο(G).用T和Pn分別表示樹圖和n個(gè)頂點(diǎn)的路圖.對任意X?V(G),G[X]表示圖G的一個(gè)由頂點(diǎn)集X導(dǎo)出的子圖.其他未加定義的符號和術(shù)語,參考文獻(xiàn)[1].

在介紹圖的零強(qiáng)迫數(shù)之前,首先回顧一個(gè)染色規(guī)則:給圖G的頂點(diǎn)集V(G)中染黑白兩種顏色,設(shè)S?V(G)是G中所有染黑色的點(diǎn)集.對任意的點(diǎn)v∈S,v的所有鄰點(diǎn)中僅有點(diǎn)u為白色,那么點(diǎn)v強(qiáng)迫點(diǎn)u染成黑色,這個(gè)染色過程稱為強(qiáng)迫過程.從頂點(diǎn)集S開始,交替運(yùn)用染色規(guī)則,最終使得G中所有點(diǎn)變?yōu)楹谏?那么點(diǎn)集S稱為G的一個(gè)零強(qiáng)迫集,而G的零強(qiáng)迫集中最小的頂點(diǎn)數(shù)目稱為G的零強(qiáng)迫數(shù),記為Z(G).

近年來,關(guān)于零強(qiáng)迫數(shù)的研究吸引了越來越多的學(xué)者關(guān)注,例如Amost 等[2]給出了圖的零強(qiáng)迫數(shù)的上界:對具有n個(gè)頂點(diǎn)的簡單連通圖G,有Z(G)≤(n(Δ-2)+2)/Δ-1,其中Δ≥2.近期,Oboudi[3]研究了樹圖T的零強(qiáng)迫數(shù)與其最大度之間的關(guān)系,證明了Z(T)≥Δ(T)-1,并刻畫了所有滿足Z(T)=Δ(T)-1 的樹圖.受到上述文獻(xiàn)的啟發(fā),本文進(jìn)一步刻畫了所有滿足Z(T)=Δ(T)的樹圖.

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

首先介紹幾類樹圖.

類型1設(shè)T(n1,…,nk)是如圖1 所示的樹圖,其中ni≥1,i=1,…,k且n=n1+…+nk-k+1,k是正整數(shù).顯然T(n1,…,nk)是一條路或者是星形樹（只有一個(gè)頂點(diǎn)的度大于2的樹）.

圖1 類型1中的樹圖T(n1,…,nk)Fig.1 Tree graph T(n1,…,nk)in type one

類型2設(shè)T(m1,…,mk;n1,…,nk)是如圖2 所示的樹圖,其中mi≥0,ni≥0,i=1,…,k且n=m1+…+mk+n1+…+nk+k+1,k是正整數(shù).樹T(1,2,0,1;2,1,0,0)如圖3所示.

圖2 類型2中的樹圖T(m1,…,mk;n1,…,nk)Fig.2 Tree graph T(m1,…,mk;n1,…,nk)in type two

圖T(n1,…,nk)和圖T(m1,…,mk;n1,…,nk)的最上層的頂點(diǎn)稱為樹圖的根點(diǎn).如圖1的頂點(diǎn)1是它的根點(diǎn),圖2和圖3的根點(diǎn)分別是v和u.

圖3 類型2中的樹圖T(1,2,0,1;2,1,0,0)Fig.3 Tree graph T(1,2,0,1;2,1,0,0)in type two

注1當(dāng)n1≥2,…,nk≥2 時(shí),上述的兩種圖形可以進(jìn)行轉(zhuǎn)換,則有T(n1,…,nk)=T(n1-2,…,nk-2;0,…,0)；其次T(n1,…,nk)和T(m1,…,mk;n1,…,nk)的根點(diǎn)只有一個(gè).此外,零強(qiáng)迫集簡稱為強(qiáng)迫集,零強(qiáng)迫數(shù)簡稱為強(qiáng)迫數(shù).

類型3對于以下四類樹圖T1,T2,T3,T4它們兩個(gè)之間通過連接一條新邊而得到三類新的樹圖ξ1,ξ2,ξ3,其如下所示：

1）ξ1表示通過一條邊連接圖T1的根點(diǎn)和圖T2的任意懸掛點(diǎn)得到的圖.

2）ξ2表示通過一條邊連接圖T1的根點(diǎn)和圖T3的根點(diǎn)的任意度為2的鄰點(diǎn)得到的圖.

3）ξ3表示通過一條邊連接圖T4的根點(diǎn)和圖T2的任意一點(diǎn)得到的圖,且滿足圖T4的根點(diǎn)是圖ξ3的最大度頂點(diǎn).

其中ξ1和ξ2階數(shù)為n=m1+…+mk-1+n1+…+nk-2+m1'+m2'+m3'+n1'+k+4,ξ3的階數(shù)為n=m''1+…+m''k-1+n''1+…+n''k-3+m1'+m2'+m3'+n1'+k+4,且k=Δ(ξi)≥3,k是整數(shù),i=1,2,3.

下面給出一些引理.

引理1[3]設(shè)T≠P1是一個(gè)具有n個(gè)頂點(diǎn)的樹圖,則Δ(T)-1≤Z(T)≤p(T)-1.

注2由引理1可得,當(dāng)T不是Pn(n≥2)時(shí),Δ(T)≥3,則Z(T)≥2.

引理2[3]設(shè)T是一個(gè)具有n≥3 個(gè)頂點(diǎn)的樹圖,則Z(T)=Δ(T)-1 當(dāng)且僅當(dāng)T=Pn或T=T(m1,…,mk;n1,…,nk-2,0,0),其 中k=Δ(T)≥3,n=m1+…+mk+n1+…+nk-2+k+1 和m1≥0,…,mk≥0,n1≥0,…,nk-2≥0.

引理3[3]設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)的連通圖,任意v∈V(G),v1,…,vt是G的懸掛點(diǎn)且N(v)={v1,…,vt},令S是G的任意一個(gè)零強(qiáng)迫集,則|S∩{v1,…,vt}|≥t-1.

引理4[4]設(shè)G是一個(gè)具有n≥2個(gè)頂點(diǎn)的連通圖,對任意v∈V(G)或e∈E(G),有Z(Gv)-1≤Z(G)≤Z(Gv)+1或Z(Ge)-1≤Z(G)≤Z(Ge)+1.

引理5[4]設(shè)G為具有n個(gè)頂點(diǎn)的連通圖,其割點(diǎn)為v.令V(Gv)=W1∪W2∪…∪Wk,其中,W1,…,Wk是Gv的各個(gè)連通分支的頂點(diǎn)的集合,Gi=G[Wi∪{v}]是由頂點(diǎn)集Wi∪{v}的導(dǎo)出子圖,其中,1≤i≤k,則Z(G)≥+1.

引理6[5]設(shè)G是具有n個(gè)頂點(diǎn)的連通圖,則Z(G)=1當(dāng)且僅當(dāng)圖G是路Pn(n≥1).

引理7設(shè)G是一個(gè)通過一條邊連接圖H中的一個(gè)頂點(diǎn)v和圖T(n1,…,nk)的根點(diǎn)得到的圖,其中H是連通圖,k=Δ(T(n1,…,nk))≥2和n1≥2,…,nk≥2,則Z(G)=Z(H)+k-1.

證明注意到點(diǎn)v是圖G的一個(gè)割點(diǎn),則Gv至少有2 個(gè)連通分支.由引理2 和引理5 可得Z(G)≥Z(H)+Z(T(n1,…,nk+1)-2+1=Z(H)+k-1.令ST是圖T(n1,…,nk)的任意k-1 個(gè)懸掛點(diǎn)的集合,顯然ST是圖T(n1,…,nk)的一個(gè)強(qiáng)迫集.假設(shè)SH是圖H的任意一個(gè)強(qiáng)迫集,容易驗(yàn)證ST∪SH是圖G的一個(gè)強(qiáng)迫集,則有Z(G)≤k-1+Z(H)≤|ST∪SH|,因此Z(G)=Z(H)+k-1,證畢.

2 主要結(jié)論

文獻(xiàn)[3]證明了樹圖T的零強(qiáng)迫數(shù)滿足Z(T)≥Δ(T)-1,并刻畫了滿足Z(T)=Δ(T)-1的所有樹圖.下面進(jìn)一步刻畫滿足Z(T)=Δ(T)的所有樹圖.

定理1設(shè)T為具有n≥2個(gè)頂點(diǎn)的樹圖,則Z(T)=Δ(T)當(dāng)且僅當(dāng)T為以下樹圖:

1)P2；

2)T(m1,…,mk;n1,…,nk-1,0),其中,m1≥1,…,mk-1≥1,n1≥1,…,nk-1≥1,mk≥0和k=Δ(T)≥3；

3)ξi,i=1,2,3.

證明充分性當(dāng)T為上述中的三種圖形,容易驗(yàn)證Z(T)=Δ(T).

必要性設(shè)T是任一樹圖,其最大度為Δ=Δ(T)且Z(T)=Δ(T),對Δ進(jìn)行討論.

當(dāng)Δ=1時(shí),此時(shí)n=2,顯然,T=P2,由引理6,可得Z(P2)=1,滿足Z(T)=Δ.

當(dāng)Δ=2時(shí),此時(shí)n≥3,顯然,T=Pn,由引理6,可得Z(Pn)=1=Δ-1,不滿足Z(T)=Δ.

當(dāng)Δ≥3時(shí),因?yàn)閆(T)=Δ,不妨令點(diǎn)v是T的最大度頂點(diǎn),即d(v)=Δ,且v1,…,vΔ是點(diǎn)v的鄰點(diǎn).由于點(diǎn)v是T的割點(diǎn),則Tv有Δ個(gè)分支,用T1,…,TΔ來表示.若T1,…,TΔ中有兩個(gè)或兩個(gè)以上不是路,由注2,引理4和引理6可得

與假設(shè)Z(T)=Δ矛盾.所以只需要考慮以下兩種情況:

情況1T1,…,TΔ都為路；

情況2T1,…,TΔ僅有一個(gè)不為路.

下面對這兩種情況進(jìn)行討論.不失一般性,對T(m1,…,mΔ;n1,…,nΔ)類型的樹圖,假設(shè)mi≥ni≥0,i=1,…,Δ.

針對情況1,由于T1,…,TΔ是路,可知T=T(m1,…,mΔ;n1,…,nΔ).對于圖形T(m1,…,mΔ;n1,…,nΔ)有以下三種情況.

情況1.1假設(shè)n1≥1,…,nΔ≥1,則m1≥1,…,mΔ≥1.下面對頂點(diǎn)數(shù)n進(jìn)行數(shù)學(xué)歸納來證明Z(T)≥Δ+1.當(dāng)頂點(diǎn)數(shù)n=3Δ+1 時(shí),即當(dāng)m1=…=mΔ=1 時(shí),則n1=…=nΔ=1,vi鄰接著2 個(gè)懸掛點(diǎn),記為xi和yi,其中i=1,…,Δ.由引理3 可得,對于樹圖T的任意一個(gè)強(qiáng)迫集S,都有xi∈S或yi∈S,則|S|≥Δ.假設(shè)|S|=Δ,由于|S∩{xi,yi}|=1,則S?{x1,y1;…;xΔ,yΔ}.在染色過程中,vi被xi或yi強(qiáng)迫染為黑色,但最終每個(gè)vi都有2 個(gè)白色的鄰點(diǎn),得到矛盾,所以|S|≥Δ+1,即是Z(T(1,…,1;1,…,1))≥Δ+1.假設(shè)頂點(diǎn)數(shù)為n-1時(shí),仍有Z(T)≥Δ+1結(jié)論成立.現(xiàn)在證頂點(diǎn)數(shù)為n的情況.假設(shè)max{m1,…,mΔ,n1,…,nΔ}≥2,不失一般性,假設(shè)m1≥2.設(shè)x是T1的懸掛點(diǎn),使得dT(x,v1)=m1,且y是x的鄰點(diǎn),e=xy,則Te分別是圖P1和圖T(m1-1,m2,…,mΔ;n1,…,nΔ).運(yùn)用歸納假設(shè)可得

由引理4可得Z(T)≥Z(Te)-1 ≥Δ+1,與假設(shè)Z(T)=Δ矛盾.

情況1.2當(dāng)ni=0,i∈{1,…,Δ},其余n1≥1,…,ni-1≥1,ni+1≥1,…,nΔ≥1.由引理1和引理2,可得Z(T)≠Δ-1 且Z(T)≥Δ-1,則Z(T)≥Δ,滿足假設(shè)Z(T)=Δ.不失一般性,假設(shè)nΔ=0,其余n1≥1,…,nΔ-1≥1,則m1≥1,…,mΔ-1≥1,mΔ≥0.在圖T(m1,…,mΔ;n1,…,nΔ-1,0)中取點(diǎn)集如下:當(dāng)mi=0 時(shí),取wi=vi；當(dāng)mi≠0,取wi=ui,其中ui是Ti的懸掛點(diǎn),滿足dT(ui,vi)=mi,其中i∈{1,…,Δ}.令點(diǎn)集S={w1,…,wΔ},容易驗(yàn)證S是圖T(m1,…,mΔ;n1,…,nΔ-1,0) 的一個(gè)強(qiáng)迫集,則Z(T)≤|S|=Δ,從而Z(T)=Δ,那 么樹圖T=T(m1,…,mΔ;n1,…,nΔ-1,0).

情況1.3當(dāng)ni=nj=0(i≠j),i,j∈{1,…,Δ},其余為非負(fù)整數(shù).由引理2 可得,Z(T)=Δ-1,與假設(shè)Z(T)=Δ矛盾.

針對情況2,不失一般性,假設(shè)TΔ不是路,顯然Z(TΔ)=2.否則,Z(TΔ)≥3,根據(jù)引理4和引理6可得

即Z(T)≥Δ+1,與假設(shè)Z(T)=Δ矛盾.進(jìn)一步由引理2 可知Z(TΔ)=2 當(dāng)且僅當(dāng)TΔ=,其中.

記I1=,當(dāng)=0；記I2=,當(dāng)≥1.在樹圖T中,最大度頂點(diǎn)v與TΔ鄰接的點(diǎn)為vΔ,不妨令v與vΔ鄰接的邊為e.由于Δ≥3,T1,…,TΔ-1分支是路,那么v與T1,…,TΔ-1鄰接得到的圖記為T(m1,…,mΔ-1;n1,…,nΔ-1),下面對圖T(m1,…,mΔ-1;n1,…,nΔ-1)進(jìn)行討論,與情況1證明類似,同理對于圖T(m1,…,mΔ-1;n1,…,nΔ-1)分以下三種情況.

情況2.1當(dāng)n1≥1,…,nΔ-1≥1時(shí),那么m1≥1,…,mΔ-1≥1,根據(jù)情況1.1可得

Z(T(m1,…,mΔ-1;n1,…,nΔ-1))≥Δ.在整個(gè)樹圖T中,根據(jù)引理4可得

即Z(T)≥Δ+1,與假設(shè)Z(T)=Δ矛盾.

情況2.2當(dāng)僅存在一個(gè)i∈{1,…,Δ-1}使得ni=0.不失一般性,假設(shè)nΔ-1=0,其余的n1≥1,…,nΔ-2≥1,那么m1≥1,…,mΔ-2≥1,mΔ-1≥0,這個(gè)圖記為

T1=T(m1,…,mΔ-1;n1,…,nΔ-2,0),由引理1,引理2可得Z(T1)≥Δ-1.在整個(gè)樹圖T中,根據(jù)引理4可得

即Z(T)≥Δ,滿足假設(shè)Z(T)=Δ.此情況下的樹圖T是通過一條邊連接T1的根點(diǎn)v和TΔ的點(diǎn)vΔ得到的圖形,接下來對TΔ中的點(diǎn)vΔ討論如下.

當(dāng)d(vΔ)=3 時(shí),注意,此時(shí)的Δ≥4,否則與根點(diǎn)v是最大度頂點(diǎn)矛盾.由TΔ=I1或TΔ=I2,TvΔ得到T1和3個(gè)路Pn(n≥1).根據(jù)引理4和引理6可得

即Z(T)≥Δ+1,與假設(shè)Z(T)=Δ矛盾.

當(dāng)d(vΔ)=2時(shí),且TΔ=I1,此時(shí)Δ≥3,考慮以下兩種情況.

1)當(dāng)vΔ是TΔ的根點(diǎn)的鄰點(diǎn)時(shí),此時(shí)樹圖T等同于通過一條邊連接圖T(N1,N2)(N1,N2是不小于2 的整數(shù))的根點(diǎn)與圖T(m1,…,mΔ,n1,…,nΔ-2,0,0)的點(diǎn)vΔ得到的圖.根據(jù)引理2和引理7可得

即Z(T)=Δ,此時(shí)樹圖T=ξ2.

2)當(dāng)vΔ不是TΔ的根點(diǎn)的鄰點(diǎn)時(shí),TvΔ有3個(gè)分支,分別記為Q1,Q2,Q3,其中Q1∈T1,Q2∈I1,Q3∈Pn(n≥1).根據(jù)引理4和引理6可得

即Z(T)≥Δ+1,與假設(shè)Z(T)=Δ矛盾.

當(dāng)d(vΔ)=2 時(shí),且TΔ=I2時(shí),TvΔ都有3 個(gè)分支,分別記為Q1',Q2',Q3',其中Q1'∈T1,Q2'∈{I1,I2},Q3'∈Pn(n≥1).根據(jù)引理4和引理6可得

即Z(T)≥Δ+1,與假設(shè)的Z(T)=Δ矛盾.

當(dāng)d(vΔ)=1,TΔ=I1或TΔ=I2,此時(shí)Δ≥3.對于圖T1,與情況1.2 類似,同理找到T1的一個(gè)強(qiáng)迫集,記為S1={s1,…,sΔ-1}.在整個(gè)樹圖T中,根據(jù)染色規(guī)則,根點(diǎn)v會(huì)被T1的某個(gè)頂點(diǎn)強(qiáng)迫為黑色,且v只有一個(gè)白色鄰點(diǎn)vΔ,那么v繼續(xù)強(qiáng)迫vΔ染為黑色.由于Z(TΔ)=2,那么在TΔ中存在另外一個(gè)懸掛點(diǎn),記為u1,使得點(diǎn)集{vΔ,u1}可以將TΔ所有點(diǎn)染為黑色.容易驗(yàn)證S1∪u1是T的一個(gè)強(qiáng)迫集,則Z(T)≤|S1∪u1|=Δ.由引理1,引理2可得Z(T)≥Δ,因此Z(T)=Δ.此時(shí)的樹圖T=ξ1.

情況2.3當(dāng)ni=nj=0(i≠j),i,j∈{1,…,Δ-1},其余為非負(fù)整數(shù).不失一般性,我們假設(shè)nΔ-1=nΔ-2=0,其余的n1≥0,…,nΔ-3≥0,那么m1≥0,…,mΔ-1≥0,這個(gè)圖記為T2=T(m1,…,mΔ-1;n1,…,nΔ-3,0,0),則Z(T2)=Δ-2.在整個(gè)樹圖T中,根據(jù)引理4和引理6可得

整理可得Z(T)≥Δ,滿足假設(shè)Z(T)=Δ.此情況下,樹圖T是通過一條邊連接圖T2的根點(diǎn)v和圖TΔ的點(diǎn)vΔ得到的圖形.在根點(diǎn)v是樹圖T的最大度頂點(diǎn)條件下,vΔ是TΔ上任意一點(diǎn).在圖T2取點(diǎn)集如下:如果mi=0,令wi1=vi,如果mi≠0,則令wi1=ui,其中ui是Ti的懸掛點(diǎn),使得dT(ui,vi)=mi,i∈{1,…,Δ-2}.令點(diǎn)集S2=,容易驗(yàn)證S2是T2的一個(gè)強(qiáng)迫集.對于TΔ∈T(m1',m2',m3';n1',0,0),同理找到TΔ的一個(gè)強(qiáng)迫集,令其為點(diǎn)集S3={p1,p2},其中p1,p2∈V(TΔ).容易驗(yàn)證,S2∪S3是樹圖T的一個(gè)強(qiáng)迫集,從而Z(T)≤|S2∪S3|=Δ,即Z(T)=Δ,此時(shí)樹圖T=ξ3.證畢.