三類(lèi)特殊圖的(強(qiáng))彩虹連通數(shù)

趙燕,柴航

(泰州學(xué)院數(shù)理學(xué)院,江蘇 泰州 225300)

1 引言

本文考慮的圖為有限無(wú)向簡(jiǎn)單圖.Chartrand等人[1]在2008年首次提出了彩虹連通性的概念.設(shè)圖G=(V,E)是一個(gè)非平凡的連通圖,在G上定義一個(gè)邊染色c:E→{1,2,···,t},t∈N,其中相鄰的邊可以染相同顏色.如果這條路上的任意兩條邊均染不同顏色,稱(chēng)圖G的一條路是彩虹路.如果在圖G的任意兩個(gè)頂點(diǎn)間都存在一條彩虹路,就稱(chēng)圖G是彩虹連通的.對(duì)于一個(gè)連通圖G,保證它是彩虹連通所需的最少顏色數(shù)就是G的彩虹連通數(shù),記為rc(G).彩虹連通不僅是一個(gè)自然的組合概念,而且在網(wǎng)絡(luò)中也有著重要的應(yīng)用.事實(shí)上,它的提出起源于政府機(jī)構(gòu)之間的信息安全傳遞.當(dāng)人們?cè)跈C(jī)構(gòu)之間傳遞信息時(shí),一方面希望所用的密碼個(gè)數(shù)足夠得少以便于管理;另一方面,又需要足夠多的密碼,使得任何兩個(gè)機(jī)構(gòu)之間至少存在一條信息安全路(路的不同段分配不同密碼),以防止入侵者破壞.可以用圖來(lái)表示這個(gè)信息傳遞網(wǎng)絡(luò).如果用邊染色表示密碼,那么最少的密碼個(gè)數(shù)就是圖的彩虹連通數(shù).

基于彩虹連通數(shù)的概念,Chartrand等人[1]又提出了強(qiáng)彩虹連通數(shù)的概念.給定圖G中的兩個(gè)點(diǎn)u,v,一條彩虹(u,v)-測(cè)地線是指圖G中一條長(zhǎng)度為d(u,v)的彩虹路,其中d(u,v)表示圖G中u,v的距離.如果在圖G的任意兩個(gè)頂點(diǎn)間都存在一條彩虹測(cè)地線,就稱(chēng)圖G是強(qiáng)彩虹連通的.對(duì)于一個(gè)連通圖G,保證它是強(qiáng)彩虹連通所需的最少顏色數(shù)就是G的強(qiáng)彩虹連通數(shù),記為src(G).

Chakraborty等人[2]證明了給定一個(gè)圖G,判定rc(G)=2是NP-完全的,特別的,計(jì)算一個(gè)圖的rc(G)是NP-困難的.Chartrand等人[1]得到了一些特殊圖類(lèi)的彩虹連通數(shù).例如,rc(G)=src(G)=1當(dāng)且僅當(dāng)G是完全圖,rc(G)=src(G)=m當(dāng)且僅當(dāng)G為一棵m條邊的樹(shù),一個(gè)頂點(diǎn)數(shù)大于3的圈的 (強(qiáng))彩虹連通數(shù)為.注意到,對(duì)于任意連通圖G,diam(G)≤rc(G)≤src(G)≤m,其中diam(G)表示圖G的直徑,m表示圖G的邊數(shù).同時(shí)注意到,若H為G的連通生成子圖,則rc(G)≤rc(H).更多關(guān)于彩虹染色的結(jié)果參考文獻(xiàn)[3-6].

本文研究了兩類(lèi)特殊圖的彩虹連通數(shù).首先給出一些定義.2n個(gè)點(diǎn)的太陽(yáng)圖是在n個(gè)點(diǎn)的圈圖的基礎(chǔ)上,每個(gè)點(diǎn)處再懸掛一條邊.令圖G有m個(gè)頂點(diǎn),圖H有n個(gè)頂點(diǎn),G和H的日冕(corona)(用G⊙H表示)定義為一個(gè)圖,取一個(gè)G的復(fù)制和m個(gè)H的復(fù)制H1,···,Hm,在G的第i個(gè)點(diǎn)和H的第i個(gè)復(fù)制的每個(gè)點(diǎn)均連邊.由定義可知,G⊙H有m(1+n)個(gè)頂點(diǎn).對(duì)任意兩個(gè)圖G和H顯然有G⊙H?H⊙G.

接著給出本文需要用到的一些彩虹連通數(shù)的結(jié)果.

引理1.1[7]令n≥2,則扇圖(即Pn∨K1)的彩虹連通數(shù)為：

引理1.2[7]令n≥2,則扇圖(即Pn∨K1)的強(qiáng)彩虹連通數(shù)為：

引理1.3 令n≥3,則太陽(yáng)圖Sn的(強(qiáng))彩虹連通數(shù)為：

2 主要結(jié)果

定理2.1 令G=(Pt1∪Pt2∪···∪Pts)∨K1,其中,2≤ t1≤ t2≤···≤ ts,則

證明令

其中

s=1的情形即引理1.1,因此下設(shè)s≥2.首先令s≥3.定義一種染色方式

若1≤i≤s,1≤j≤ti,且j為奇數(shù);c(vvti,j)=2,若1≤i≤s,1≤j≤ti,且j為偶數(shù);其余邊染3色.易證圖中任意兩點(diǎn)均有彩虹路連接,因此rc(G)≤3.假設(shè)用兩種顏色染色,由于

并且vt1,i和vt2,j(vt3,k)只有一條2長(zhǎng)路,因此得到

此時(shí),vt2,j和vt3,k無(wú)彩虹路.因此rc(G)=3.

當(dāng)s=2,t2≥4時(shí),仍采用染色方式c1,可以保證圖中任意兩點(diǎn)均有彩虹路連接,因此rc(G)≤3.假設(shè)用兩種顏色染色,由于d(vt1,i,vt2,j)=2,并且vt1,i和vt2,j只有一條2長(zhǎng)路,因此得到

其中1≤j,k≤t2,j?=k.此時(shí),vt2,1和vt2,t2無(wú)彩虹路.因此rc(G)=3.

當(dāng)s=2,t2≤3時(shí),定義一種染色方式

c2:E→{1,2}:c(vvt1,1)=c(vvt1,2)=c(vvt1,3)=c(vt1,1vt1,2)=c(vt2,1vt2,2)=1,其余邊染2色.易證圖中任意兩點(diǎn)均有彩虹路連接,因此rc(G)=2.

定理2.2 令G=(Pt1∪Pt2∪···∪Pts)∨K1,其中2≤ t1≤ t2≤ ···≤ ts,s≥ 2,則

證明令

其中

s=1的情形即引理1.2,因此下設(shè)s≥2.考慮vti,p和vtj,q(i?=j).由于它們只有一條測(cè)地線,為保證vti,p和vtj,q有彩虹測(cè)地線,

由引理1.2知,如果c(vvti,p)=c(vvti,q),則dPti(vti,pvti,q)≤2.因此

另一方面,類(lèi)似于引理1.2,可以定義一種染色方式保證圖中任兩點(diǎn)有一條彩虹測(cè)地線.因此,定理得證.

定理2.3 設(shè)n為偶數(shù),令G=Cn⊙K2,則rc(G)=

證明 令n=2k.設(shè)

其中1≤i≤n.首先證明rc(G)≤k+3.定義一種染色方式

c:E → {1,2,···,k+3}: c(vivi,1)=k+1(1≤ i≤ n), c(vivi,2)=k+2(1 ≤ i≤ n),c(vi,1vi,2)=k+3(1≤i≤n), c(vivi+1)=i(1≤i≤k), c(vivi+1)=i?k(k+1≤i≤n).

易證圖中任意兩點(diǎn)均有彩虹路連接,因此得證.

下面證明rc(G)≥k+3.反證,假設(shè)G使用一種k+2種顏色的邊染色方式使得圖中任意兩點(diǎn)有一條彩虹路連接.

首先得到如下的論斷:圈中兩條同色邊只能是相對(duì)邊.反證,假設(shè)

為保證vi,1和vj+1,1存在一條彩虹路,d(vivj)=k?1.不妨假設(shè) c(v1vn)=c(vk+1vk+2).考慮v1,1(v1,2)和vk+1,1(vk+1,2).易得

于是有

不妨假設(shè)

為保證vk+1,1和vk,1,vk+1,1和vk,2均有彩虹路,色k和k+2不能同時(shí)出現(xiàn)在vk懸掛的三角形中. 考慮v1,1和vk,1(vk,2),此時(shí)v1,1vk,1-彩虹路只可能走vkvk,1或者vkvk,2vk,1. 如果走vkvk,1,v1,1vk,1必為色k或k+2.如果為色k,為保證v1,1和vk,2有彩虹路,vk,1vk,2染k+2或者vkvk,2染k或k+2,此時(shí)vk+1,1和vk,1無(wú)彩虹路,矛盾.如果為色k+2,為保證v1,1和vk,2有彩虹路,vk,1vk,2染k或者vkvk,2染k或k+2,此時(shí)vk+1,1和vk,1仍無(wú)彩虹路,矛盾. 如果走v1,1vk,2vk,1,v1,1vk,2和vk,2vk,1必為色k和k+2,此時(shí)vk,2和vk+1,2無(wú)彩虹路,矛盾.

為保證v1,1和vk+1,1有彩虹路,不妨假設(shè)

由上述論斷知,色k+1在圈中至多出現(xiàn)一次,k+2也至多出現(xiàn)一次.根據(jù)色k+1和k+2是否在圈中,分如下三種情形考慮.

情形1 色k+1和k+2同時(shí)在圈中.此時(shí)

進(jìn)一步,只能邊vk+1vk+2染色k+1,邊vnv1染色k+2.由上述論斷知,

考慮v1,1和vk,1,如果vkvk,1染色k,為保證v1,1和vk,2有彩虹路,則vk,1vk,2染k+2或者vkvk,2染k或k+2,此時(shí)vk,1和vk+1,2無(wú)彩虹路,矛盾;如果vkvk,1染色k+2,類(lèi)似vkvk,1染色k的情形;如果vkvk,1不染色k和k+2,則vkvk,2和vk,2vk,1必為色k和k+2,此時(shí)vk,2和vk+1,2無(wú)彩虹路,矛盾.

情形2 色k+1在圈中,色k+2不在圈中(色k+2在圈中,色k+1不在圈中類(lèi)似).此時(shí)

進(jìn)一步,只能vk+1vk+2染色k+1.由上述論斷得

類(lèi)似于情形1,考慮v1,1和vk,1,均會(huì)得出矛盾.

情形3 色k+1和k+2均不在圈中.

由上述論斷知,c(vivi+1)=i?k(k+1≤i≤n?1).此時(shí)

類(lèi)似于情形1,考慮v1,1和vk,1(vk,2),色k+2或者色k出現(xiàn)在vk懸掛的三角形中兩次,或者色k和k+2同時(shí)出現(xiàn)在vk懸掛的三角形中,均會(huì)得出矛盾.

推論2.1 設(shè)n≥4為偶數(shù),令G=Cn⊙P3,則rc(G)=

證明設(shè)

其中1≤i≤n.在定理2.3的染色基礎(chǔ)上,添加新的染色

通過(guò)類(lèi)似定理2.3的討論,可以得證.

定理2.4 設(shè)n≥4為偶數(shù),令G=Cn⊙K2,則src(G)=n+1.

證明設(shè)

其中1≤i≤n.首先證明src(G)≤n+1.定義一種染色方式c:E→{1,2,···,n+1},其中

易證圖中任意兩點(diǎn)均有彩虹測(cè)地線連接,因此c為強(qiáng)彩虹連通染色.

下證

用反證方法,假設(shè)src(G)≤n.由于

推論2.2 設(shè)n≥4為偶數(shù),令G=Cn⊙P3,則src(G)=n+1.

證明設(shè)

其中,1≤i≤n.在定理2.4的染色基礎(chǔ)上,添加新的染色

通過(guò)類(lèi)似定理2.4的討論,可以得證.