直徑為2的有向圖的彩虹連通*

龍漢青,　于克凡,　張必成

(湘潭大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院, 湖南 湘潭 411105)

圖的連通度是圖論中的基本研究對(duì)象. 有許多方式去強(qiáng)化這個(gè)概念, 比如要求哈密頓性,k-連 通性, 限定直徑的值,等等. 一種有趣的強(qiáng)化——彩虹連通, 在2008年首先由Chartrand G等學(xué)者在[1]中提出. 這個(gè)新概念來(lái)自政府與下級(jí)機(jī)構(gòu)間的信息傳輸. “911”事件等致命襲擊的一個(gè)意想不到的后果是使得執(zhí)法機(jī)構(gòu)和情報(bào)機(jī)構(gòu)無(wú)法通過(guò)正常渠道相互溝通.為了保護(hù)涉及國(guó)家安全的信息,同樣需要保證部門之間能夠準(zhǔn)確通訊.這兩方面的問(wèn)題可以通過(guò)設(shè)計(jì)部門間的信息傳輸通道(可能需要其他部門作為中間傳輸者)來(lái)解決.這需要大量的密碼以抵御網(wǎng)絡(luò)入侵者.為了便于管理,密碼又需盡可能的少.保證部門間通信渠道所需要密碼均兩兩不同的最小密碼數(shù)是多少？這個(gè)問(wèn)題可以通過(guò)圖論語(yǔ)言來(lái)描述.用頂點(diǎn)代表機(jī)構(gòu),邊代表機(jī)構(gòu)間的溝通渠道,把所得到的圖記為G.用不同顏色代表不同密碼,則所要求的最小密碼數(shù)就是圖G的彩虹數(shù)cr(G).

我國(guó)學(xué)者李學(xué)良教授的團(tuán)隊(duì)在圖的彩虹連通方面做了大量的研究,他們研究了稠密圖[2],3-連通圖[3],直徑為2的圖[4]等一系列圖的相關(guān)性質(zhì).圖的彩虹數(shù)與其他參數(shù),比如最小度,連通控制數(shù),連通度之間的聯(lián)系以及圖與其線圖,補(bǔ)圖的彩虹數(shù)的關(guān)系在[5]～[9]中被研究.更詳細(xì)的內(nèi)容可參見(jiàn)綜述文章[10].

作為無(wú)向圖的彩虹連通的推廣,有向圖的彩虹連通這一概念由Dorbec P等學(xué)者于2014年在[11]中提出.有向圖的彩虹連通方面的研究工作較少.[11]和[12]分別研究了競(jìng)賽圖和循環(huán)有向圖的彩虹連通.

在本文中我們考慮直徑為2的有向圖的彩虹連通.

為了方便起見(jiàn),下面介紹一些必要的概念.本文未提及的符號(hào)和術(shù)語(yǔ)與[13][14]一致.

設(shè)D={V,E}是直徑為2的有向圖,對(duì)任意給定頂點(diǎn)v∈V,令N1:=N+(v)N-(v),N2:=N+(v)∩N-(v),N3:=N-(v)N+(v).令頂點(diǎn)集V的子集R滿足R=V({v}∪N1∪N2∪N3).如圖1所示,將E(v,V)和E(V,v)中的弧分別著顏色1和5；E(R,N1∪N2∪N3)和E(N1∪N2∪N3,R)中的弧分別著顏色3和2；弧集E(N2,N3),E(N1,N2),E(N1,N3)中的弧分別著顏色2,3和4；D[N1],D[N2],D[N3],D[R]中的弧分別著顏色5,4,1,5；剩余的弧用顏色1,2,3,4,5任意著色.

定理2設(shè)k-正則有向圖D={V,E}的直徑為2,那么

如果k2≤2μ1-4,那么

注意到對(duì)于具有參數(shù)(n,k,μ,λ,t)的有向強(qiáng)正則圖D,μ1(D)=μ2(D)=μ.

如圖4中的有向圖為6階的有向強(qiáng)正則圖D,它的參數(shù)集(n,k,μ,λ,t)=(6,2,1,0,1).注意到該圖僅使用兩種顏色的彩虹著色,如果存在,一定是強(qiáng)彩虹著色,而在這樣的強(qiáng)彩虹著色下,由μ=1知“外圍三角形”一定是“彩虹”的,與著色僅使用兩種顏色矛盾,故D的彩虹數(shù)至少為3,實(shí)際上D的彩虹數(shù)與強(qiáng)彩虹數(shù)皆為3,圖4給出了一種僅用3種顏色的強(qiáng)彩虹著色.

[1]CHARTRAND G, JOHNS G L,MCKEON K A ，et al.Rainbow connection in graphs[J].Mathematica Bohemica,2008,133(1):85-98.

[2]LI X, LIU M,SCHIERMEYER I. Rainbow connection number of dense graphs[J].Discussiones Mathematicae Graph Theory,2013，33(3):603-611.

[3]LI X,SHI Y. Rainbow connection in 3-connected graphs[J]. Graphs and Combinatorics,2013,29(5):1471-1475.

[4]LI H, LI X,LIU S.Rainbow connection of graphs with diameter 2[J].Discrete Mathematics,2012,312(8):1453-1457.

[5]KRIVELEVICH M, YUSTER R.The rainbow connection of a graph is (at most) reciprocal to its minimum degree[J].Journal of Graph Theory,2010,63(3):185-191.

[6]SUNIL CHANDRAN L,DAS A, RAJENDRAPRASAD D,et al.Rainbow connection number and connected dominating sets[J].Journal of Graph Theory,2012,71(2):206-218.

[7]LI X,LIU S, CHANDRAN L S,et al.Rainbow connection number and connectivity[J].The Electronic Journal of Combinatorics,2012,19(1):20.

[8]LI X, SUN Y.Rainbow connection numbers of line graphs[J].Ars Comb,2011,100:449-463.

[9]CHEN L, LI X, LIAN H. Nordhaus-gaddum-type theorem for rainbow connection number of graphs[J].Graphs and Combinatorics,2013:1-13.

[10]LI X,SHI Y, SUN Y.Rainbow connections of graphs:a survey[J].Graphs and Combinatorics，2013:1-38.

[11]DORBEC P,SCHIERMEYER I, SIDOROWICZ E,et al.Rainbow connection in oriented graphs[J].Discrete Applied Mathematics,2014,179:69-78.

[12]ALVA-SAMOSJ,MONTELLANO-BALLESTEROS J J. Rainbow connection in some digraphs[J].Graphs and Combinatorics，2016,32(6):2199-2209.

[13]BONDY J A,MURTY U S R. Graph theory with applications[M].Citeseer,1976：290.

[14]DUVAL A M.A directed graph version of strongly regular graphs[J].Journal of Combinatorial Theory, Series A,1988,47(1):71-100.

[15] ALON N, SPENCER J H.The probabilistic method[M]. John Wiley & Sons, 2004.