圖的修正的k-頂點彩虹連通度

王萬禹，王成強

(1.四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院，四川成都 610066；2.成都師范學(xué)院數(shù)學(xué)學(xué)院，四川成都 610030)

首先給出文中需要的一些定義.

定義1[8]如果路P中所有頂點著不同的顏色，或者除端點外其余內(nèi)點著不同于端點的顏色且內(nèi)點染色各不相同,也就是說路P中只有兩個端點可以著相同的顏色,那么路P稱為修正的頂點彩虹路.

定義2[8]如果圖中任意兩個頂點至少由一條修正的頂點彩虹路連接,則頂點著色c稱為修正的頂點彩虹著色.

定義3[8]如果一個修正的頂點彩虹著色圖G用了k種顏色,則稱這個圖G為k-可修正的頂點彩虹著色圖.

定義4使得圖G是修正的頂點彩虹連通圖的最小顏色數(shù)目稱為圖G的修正頂點彩虹連通度,記做rvc*k(G).

定義5對兩條u-v路P1,P2,如果V(P1)∩V(P2)={u,v},則稱P1和P2為內(nèi)部頂點不交的路.

定義6如果圖G中任意兩點間存在k條內(nèi)部頂點不交的修正的頂點彩虹路,那么圖G稱為修正的k-頂點彩虹圖.使得圖G為修正的k-頂點彩虹圖的最小顏色數(shù)稱為修正的k-頂點彩虹連通度,記為rvc*k(G).

由定義6可知,當(dāng)k=1時,rvc*1(G)=rvc*(G).只有當(dāng)圖G的點連通度κ(G)≥k時,圖的修正的k-頂點彩虹連通度才有意義.文中研究都是在這個條件下進行的.記diam(G)為圖G的直徑,那么rvc*k(G)≥diam(G),當(dāng)k=1,直徑為1時,等式成立.

定義7令M表示一個匹配,任取一邊e∈M,若e的兩個端點著不同顏色,則稱e為彩虹匹配邊.若M中每條邊都是彩虹匹配邊,則稱M為彩虹匹配.

定義8如果路P中所有的邊著不同的顏色,那么路P稱為彩虹路.

定義9如果圖中任意兩個頂點至少由一條彩虹路連接,則圖G為彩虹連通圖.使得圖G是彩虹連通圖的最小顏色數(shù)目k稱為圖G的彩虹連通度,記做rc(G).

定義10如果圖G中任意兩點間存在k條內(nèi)部頂點不交的彩虹路,那么圖G稱為k-彩虹圖.使得圖G為k-彩虹圖的最小顏色數(shù)稱為k-彩虹連通度,記為rck(G).

文中主要在頂點彩虹連通度的基礎(chǔ)上研究修正的k-頂點彩虹連通度,給出圈、輪、二部圖以及完全圖的修正的k-頂點彩虹連通度.以下[·]*表示上取整函數(shù)，[·]*表示下取整函數(shù).

1 一些圖類的修正的k-頂點彩虹連通度

定理1[8]對于任意正整數(shù)n≥3，有

定理2當(dāng)n≥3時,rvc*2(Cn)=n.

證明顯然rvc*2(Cn)≤n.記Cn的著色為c,假設(shè)rvc*2(Cn)=n-1,即對于圖Cn,可以用n-1種顏色對其著色，使其為修正的2-頂點彩虹連通圖.在這個著色過程中,有兩個頂點著色相同,記為u和v,即c(u)=c(v).

情形1.u和v相鄰.

任意選擇一點x∈V(Cn){u,v},對于兩條x-u路,一定會有一條x-u路從x出發(fā),經(jīng)過v再到u,因c(u)=c(v)，故其不是修正的頂點彩虹路.此時Cn不是修正的2-頂點彩虹連通圖.

情形2.u和v不相鄰.

情形2.1.若d(u,v)=2,則最短u-v路要經(jīng)過一點,記為x.在另外一條u-v路中,此時x-u路中有一條路xv…ux不是修正的頂點彩虹路.

情形2.2.若d(u,v)≥3,則在最短u-v路上任取兩點x,y,顯然不存在兩條修正的頂點彩虹x-y路,這與Cn是修正的2-頂點彩虹連通圖矛盾.綜合情形1-2可知，rvc*2(Cn)=n. 】

對于n≥3,輪Wn被定義為Cn+K1,K1和Cn每個頂點相連接,所以W3=K4,K1的頂點稱為中心點.下面給出輪的修正的2-頂點和3-頂點彩虹連通度.

定理3對于輪Wn,有

(b)rvc*3(Wn)=n+1.

情形1.u,v∈V(Cn).

情形1.1.u,v∈V(P1)或u,v∈V(P2),不妨設(shè)u,v∈V(P1).因為P1是修正的頂點彩虹路,故頂點全在P1中的u-v路也是修正的頂點彩虹路.由著色可知,uwv是修正的頂點彩虹路.所以有2條修正的頂點彩虹u-v路.

情形1.2.u∈V(Pi)且v∈V(Pj)(i≠j,1≤i,j≤2),不妨設(shè)u∈V(P1),v∈V(P2).如果c(u)=c(v),則在Cn上有兩條修正的頂點彩虹路.若c(u)≠c(v),則在Cn上距離較短的u-v路為修正的頂點彩虹路,另外一條u-v路不是.而uwv為修正的頂點彩虹路,所以在這種情形下,共有兩條修正的頂點彩虹u-v路.

情形2.u∈V(Cn),v=w或v∈V(Cn),u=w.

不妨設(shè)u∈V(Cn),v=w.令vi是圈上與u相鄰的一點,顯然c(u)≠c(vi)，所以uw(w=v)和uviw為兩條修正的頂點彩虹路.

由情形1和情形2可知，著色c為Wn的修正的2-頂點彩虹著色，且

(1)

情形1.x,y,z中有一個頂點為中心點w,不妨設(shè)z=w.

在Cn中任取一點u,v-x內(nèi)部不交路有3條,但是v…y…x和uwx不是修正的頂點彩虹路.故只有1條修正的頂點彩虹v-x路.這與Wn為修正的2-頂點彩虹圖矛盾.

情形2.x,y,z∈V(Cn).

由情形1和情形2知

(2)

綜合(1)-(2)式可知，當(dāng)n≥4時，有

(b)因為Wn為3-連通圖,故任意兩點間有3條內(nèi)部點不交的路.顯然rvc*3(Wn)≤n+1成立.現(xiàn)在假設(shè)rvc*3(Wn)=n,那么Wn中有兩個頂點著相同色,記為u,v.記Wn=Cn+K1,設(shè)中心點w=K1.

情形1.u,v∈Cn.

在Cn上選擇和點u相鄰的頂點x,因為3條u-x路中必定有一條要經(jīng)過點v,而u…v…x路不為彩虹路,所以只有2條修正的頂點彩虹u-x路,矛盾.

情形2.u∈Cn,v=w.

任選Cn上不同于u的一點x,因為三條u-x路中必定有一條要經(jīng)過點v(v=w),而u…v(v=w)…x路不為彩虹路,所以只有2條修正的頂點彩虹u-x路,矛盾.

由情形1和情形2知,rvc*3(Wn)≥n+1.所以rvc3(Wn)=n+1. 】

命題1圖G為完全二部圖,令M表示含k條邊的彩虹匹配,對于任意兩點u,v?V(M),如果uv的著色和M中頂點顏色不同,則至少存在k條頂點不交的修正的頂點彩虹u-v路.

證明因為圖G為完全二部圖,設(shè)G=V1,V2,E,M={x1y1,x2y2,…,xkyk}，其中xi∈V1,yi∈V2(1≤i≤k).如果u∈V1,v∈V2,則路u-xi-yi-v(1≤i≤k)為修正的頂點彩虹路,共k條.另一方面，不妨設(shè)u,v∈V1,此時路u-yi-v為修正的頂點彩虹路，共k條. 】

命題2令M為含k-1條邊的完美匹配,若M中有k個頂點著相同顏色,則至少存在一條邊e∈M,使得e的兩個端點著相同顏色.

證明因為M為含k-1條邊的完美匹配,令M={x1y1,x2y2,…,xk-1yk-1}.設(shè)X={x1,x2,…,xk-1},Y={y1,y2,…,yk-1}.如果X中的頂點有s(1≤s≤k-1)個頂點著色相同，不妨設(shè)為前s個頂點(x1,x2,…,xs).當(dāng)s=1或者k-1時,結(jié)論顯然成立.現(xiàn)在假設(shè)2≤s≤k-2,因為M中有k個頂點著相同顏色,所以在Y中有k-s個頂點著色和X中前s個頂點著色相同.如果y1,y2,…,ys著色和X中前s個頂點著色不同，則在Y中剩余的k-1-s個頂點中需要有k-s個頂點和X中前s個頂點著色相同，矛盾. 】

定理4令G=Kp,q(p≤q)為k連通圖,則k≤p，且有

(a)rvc*(Kp,q)=2;

(b)rvc*k(Kp,q)=k+2,p≥2k-2;

(c)rvc*2(Kp,q)=4.

證明(a)令X表示含圖G第一部分p個頂點的頂點集,Y表示含圖G第二部分q個頂點的頂點集,即X={v1,v2,…,vp},Y={u1,u2,…,uq}.

給X中所有頂點著色1,Y中所有頂點著色2,任意兩點間存在一條修正的頂點彩虹路,故rvc*(Kp,q)≤2.給G中所有頂點著色1,對任意x∈V(X),y∈V(Y),u和v之間不存在修正的頂點彩虹路,故rvc*(Kp,q)≥2.所以rvc*(Kp,q)=2.

(b)將頂點集X拆分成k個子集,記為{X1,X2,…,Xk},滿足條件X=X1∪X2∪…∪Xk,X2=X3=…=Xk,X1=p-k+1.因為G為完全二部圖,所以存在G的一個完備匹配M滿足條件M=M1∪M2∪…∪Mk且V(Mi)∩V(Mj)=?(i≠j),其中Mi為頂點子集Xi(1≤i≤k)到Y(jié)中某一頂點子集Yi之間的完備匹配且Mi=Xi.

當(dāng)p=q時M為完美匹配.接下來給出G的一個著色法c:X1中所有點著色1,Xi(2≤i≤k)著色2.Yi的著色記為c(Yi)=i+2(1≤i≤k).若p

下面證明著色c為圖G的修正的k-頂點彩虹著色.先討論p=q的情形,此時圖G為正則的完全二部圖.任取兩點u和v.

情形1.u,v分別在X1和Y1上.

不妨設(shè)u∈X1,v∈Y1.此時除含X1的頂點的匹配外，還有k-1條彩虹匹配.由命題1知,除uv路外，還有k-1條內(nèi)部頂點不交的修正的頂點彩虹路.

情形2.u?X1或者v?Y1.

情形2.1.當(dāng)u?X1且v?Y1時,如果u,v來自于XX1或YY1,此時有p條內(nèi)部頂點不交的修正的彩虹u-v路.如果有一點，不妨令為u使得u∈XX1,則另一點v∈YY1,此時有p-k+2條修正的彩虹u-v路,因為p≥2k-2,所以p-k+2≥k.

當(dāng)q≥p+2時,結(jié)合上述p=q討論,任取兩點u,v,我們只需討論以下3種情況.

由上述討論知,c是圖G的修正的k-頂點彩虹著色,所以當(dāng)p≥2k-2時,rvc*k(Kp,q)≤k+2.

先討論p=q的情形.因為rvc*k(Kp,q)=k+1,故2k(p=q)或2k+1(p

情形1.若X的k部分頂點著相同顏色(此情形和Y中k部分頂點著相同顏色情形相同).此時c(Yi)≠c(Yj)(i≠j,1≤i≤k))且和X中頂點著色不同.取u∈X,v∈Yi,則有且僅有一條u-v修正的頂點彩虹路,即uv,矛盾.

情形2.X中有s個以及Y中有t個頂點子集著相同色,滿足s+t=k,s,t≠0.

情形2.1.c(X1)=c(Y1).取u∈X,v∈Y2.因為c(X1)=c(Y1),故經(jīng)過M1中的邊的u-v路不是修正的頂點彩虹路，故至多有k-1條內(nèi)部不交的修正的頂點彩虹u-v路.

情形2.2.c(X1)≠c(Y1).

( i )假設(shè)X中s個頂點子集(含X1),不妨設(shè)s個部分為X1,X2,…,Xs和Y中t=k-s個頂點子集(不含Y1),不妨記為Yi1,Yi2,…,Yik-s著相同顏色1,X和Y中剩余的共k個子集著不同于1的顏色且每個部分著一個新的顏色,顏色集為{2,3,…,k+1}.取u∈Y1,v∈X2，由劃分X=X1∪X2∪…∪Xk,X2=X3=…=Xk,X1=p-k+1可知,此時內(nèi)部頂點不交的修正的頂點彩虹u-v路有p-(p-k+1)-(s-1)=k-s(≤k-1)條,矛盾.

( ii ){X2,X3,…Xk}中有s個頂點子集和Y中k-s個頂點子集(含Y1)著相同顏色.記s個子集為{Xi1,Xi2,…,Xis},Y的含Y1的k-s個子集,不妨記為{Y1,Y2,…,Yk-s}.取u∈X1,v∈Y2，同情形2.2，有k-s(≤k-1)條內(nèi)部頂點不交的修正的頂點彩虹u-v路,矛盾.

由上述證明可知，當(dāng)p=q時,rvc*k(Kp,q)=k+2(p≥2k-2).

由p=q的討論可知,當(dāng)圖G的著色數(shù)為k+2時,若u∈Yj,則對于任意點v,至少有k條內(nèi)部不交的修正的頂點彩虹路.因此,只需要再討論以下兩種情況即可.

(1)v∈Yk+1,u∈Yj.在p=q的情況下,按照對圖G的著色,當(dāng)u∈Yj時,對于任意點w,都至少有k條內(nèi)部不交的修正的頂點彩虹w-v路.現(xiàn)在c(u)=c(v),故對于任意w≠u,至少有k條v-w內(nèi)部不交的修正的頂點彩虹路.當(dāng)w=v時,有p(≥k)條內(nèi)部不交的修正的頂點彩虹路.

(2)v∈Yk+1,u∈Yk+1,此時q≥p+2.由著色c可知，有p(≥k)條內(nèi)部不交的修正的頂點彩虹u-v路.

故對于p

由(b)知,當(dāng)k=2時，(c)顯然成立. 】

定理5對于完全圖Kn，有

(a)rvc*(Kn)=1;

(b)rvc*k(Kn)=k+1,2≤k≤n-1.

證明(a)顯然成立.

(b)設(shè)Kn的頂點集為V={v1,v2,…,vn}，則Kn包含一個Hamilton圈,記為Cn，且Cn為Kn的一個生成子圖.令Cn=v1v2…vnvn+1(vn+1=v1).從n個頂點中任選k個,記含這k個頂點的集合為X={vi1,vi2,…,vik},剩余頂點組成的集合記為Y=VX.現(xiàn)在給出Cn的一個點著色c.對于X中每一個不同的頂點著不同的顏色,共需要k種顏色,記這k種顏色為{1,2,…,k}.對于Y中頂點,每一個頂點著顏色k+1.對Cn的著色一共用了k+1種顏色.接下來證明c是修正的k-頂點彩虹著色.任取圖中兩點u,v.

情形1.u,v∈X.因為Kn為完全圖,所以有n-1(≥k)條內(nèi)部不交的修正的頂點彩虹u-v路.

情形2.u∈X,v∈Y.對于任意y∈Xu,uyv是修正的頂點彩虹路,這樣的路有k-1條,而uv也是修正的頂點彩虹u-v路,所以共有k條.

情形3.u,v∈Y.對所有的x∈X，uxv都為修正的頂點彩虹路,共有k條,而uv也是彩虹頂點路,所以共有k+1條修正的頂點彩虹u-v路.

所以c為修正的k-頂點彩虹著色,因而當(dāng)2≤k≤n-1時,rvc*k(Kn)≤k+1.

假設(shè)rvc*k(Kn)=k,即用k種顏色可以使Kn為修正的k-頂點彩虹圖,那么Cn中有k-1個頂點著不同顏色,剩余的n-k+1個頂點全部著一個相同的新的顏色.記著不同顏色的k-1個頂點的集合為X,剩余頂點的集合為Y.取u∈X,v∈Y.除uv路外,對于任意點x,要使uxv為修正的頂點彩虹路只有x∈X{u},這樣的x有k-2個,加上uv,內(nèi)部不交的修正的頂點彩虹u-v路只有k-1條,矛盾.

綜上所述，當(dāng)2≤k≤n-1時rvc*k(Kn)=k+1. 】

2 rck(G)和rvc*k(G)的比較

下面給出了圈、輪、二部圖以及完全圖的修正的k-頂點彩虹連通度.一個有趣的問題就是哪些圖的rc(G)大于rvc*(G),哪些圖的rvc(G)大于rc(G),在什么情況下二者又相等.由定理4(a)可知,rvc*(K1,q)=2,而rc(K1,q)=q,當(dāng)q≥2時,rc(K1,q)≥rvc*(K1,q).現(xiàn)在來構(gòu)造一個圖G:首先給出t個頂點不交的三角,接著在每個三角中選擇一個頂點,共t個,然后將這t個頂點連接起來構(gòu)造成一個t階完全圖,能夠得到rvc*(G)=rc(G)=t+1.在這部分中,目的是比較rck(G)和rvc*k(G),希望找到一些圖使得圖的k-彩虹連通度大于其修正的k-頂點彩虹連通度.

首先構(gòu)造一個rck(G)大于rvc*k(G)的圖G.圖G是由一條路和一個星圖所構(gòu)成,具體的構(gòu)造方式如下:令P=v0v1…vt是長為t的路,然后作一個以vt為中心點含s片葉子(記為u1,u2,…,us)的星圖,這樣的圖記為Lt,s,如圖1所示.

圖Lt,s中頂點vi著色i+1(0≤i≤t),uj(1≤j≤s)著色1.容易證明rvc*(Lt,s)=t+1.對于Lt,s中的邊vivi+1(0≤i≤t-1)著色i+1,對于Lt,s中屬于星圖部分的邊(共s條)，每一條邊著一個新的顏色,這個過程一共用了t+s種顏色,容易證明rc(Lt,s)=t+s.于是,給定兩個正整數(shù)a,b,當(dāng)1≤b≤a時,存在一個圖H滿足rc(G)=a,rvc*(H)=b+1,此時H=Lb,a-b.由此可得下面結(jié)果.

定理6若兩個正整數(shù)t,s滿足1≤t

證明通過圖Lt,s按以下步驟來構(gòu)造滿足定理6的圖(如圖2):

圖1 圖Lt,s圖2 滿足定理6的圖G

Fig 1GraphLt,sFig 2GraphGsatisfying theorem 6

( i )將圖Lt,s中的頂點v1,v2,…,vt分別用含k個頂點的團Kk替代,這k個團的頂點集依次記為X1,X2,…,Xt;

( ii )v0和X1中每個頂點用邊相連,對于所有的1≤i≤t-1,Xi和Xi+1中所有頂點之間用邊相連(如果t≥2)),對于所有的1≤j≤s,uj和Xt中每一個頂點用邊相連.