王萬(wàn)禹，王成強(qiáng)

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

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

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

定義2[8]如果圖中任意兩個(gè)頂點(diǎn)至少由一條修正的頂點(diǎn)彩虹路連接,則頂點(diǎn)著色c稱(chēng)為修正的頂點(diǎn)彩虹著色.

定義3[8]如果一個(gè)修正的頂點(diǎn)彩虹著色圖G用了k種顏色,則稱(chēng)這個(gè)圖G為k-可修正的頂點(diǎn)彩虹著色圖.

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

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

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

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

定義7令M表示一個(gè)匹配,任取一邊e∈M,若e的兩個(gè)端點(diǎn)著不同顏色,則稱(chēng)e為彩虹匹配邊.若M中每條邊都是彩虹匹配邊,則稱(chēng)M為彩虹匹配.

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

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

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

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

1 一些圖類(lèi)的修正的k-頂點(diǎn)彩虹連通度

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

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

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

情形1.u和v相鄰.

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

情形2.u和v不相鄰.

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

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

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

定理3對(duì)于輪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).因?yàn)镻1是修正的頂點(diǎn)彩虹路,故頂點(diǎn)全在P1中的u-v路也是修正的頂點(diǎn)彩虹路.由著色可知,uwv是修正的頂點(diǎn)彩虹路.所以有2條修正的頂點(diǎn)彩虹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上有兩條修正的頂點(diǎn)彩虹路.若c(u)≠c(v),則在Cn上距離較短的u-v路為修正的頂點(diǎn)彩虹路,另外一條u-v路不是.而uwv為修正的頂點(diǎn)彩虹路,所以在這種情形下,共有兩條修正的頂點(diǎn)彩虹u-v路.

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

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

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

(1)

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

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

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

由情形1和情形2知

(2)

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

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

情形1.u,v∈Cn.

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

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

任選Cn上不同于u的一點(diǎn)x,因?yàn)槿龡lu-x路中必定有一條要經(jīng)過(guò)點(diǎn)v(v=w),而u…v(v=w)…x路不為彩虹路,所以只有2條修正的頂點(diǎn)彩虹u-x路,矛盾.

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

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

證明因?yàn)閳DG為完全二部圖,設(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)為修正的頂點(diǎn)彩虹路,共k條.另一方面，不妨設(shè)u,v∈V1,此時(shí)路u-yi-v為修正的頂點(diǎn)彩虹路，共k條. 】

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

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

定理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個(gè)頂點(diǎn)的頂點(diǎn)集,Y表示含圖G第二部分q個(gè)頂點(diǎn)的頂點(diǎn)集,即X={v1,v2,…,vp},Y={u1,u2,…,uq}.

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

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

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

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

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

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

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

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

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

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

先討論p=q的情形.因?yàn)閞vc*k(Kp,q)=k+1,故2k(p=q)或2k+1(p

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

情形2.X中有s個(gè)以及Y中有t個(gè)頂點(diǎn)子集著相同色,滿(mǎn)足s+t=k,s,t≠0.

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

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

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

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

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

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

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

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

故對(duì)于p

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

定理5對(duì)于完全圖Kn，有

(a)rvc*(Kn)=1;

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

證明(a)顯然成立.

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 圖Lt,s圖2 滿(mǎn)足定理6的圖G

Fig 1GraphLt,sFig 2GraphGsatisfying theorem 6

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

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