• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2018-04-20 04:31:09龍漢青于克凡張必成
    關(guān)鍵詞:有向圖正則著色

    龍漢青, 于克凡, 張必成

    (湘潭大學(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.

    猜你喜歡
    有向圖正則著色
    蔬菜著色不良 這樣預(yù)防最好
    有向圖的Roman k-控制
    蘋果膨大著色期 管理細(xì)致別大意
    剩余有限Minimax可解群的4階正則自同構(gòu)
    10位畫家為美術(shù)片著色
    電影(2018年10期)2018-10-26 01:55:48
    類似于VNL環(huán)的環(huán)
    超歐拉和雙有向跡的強(qiáng)積有向圖
    關(guān)于超歐拉的冪有向圖
    有限秩的可解群的正則自同構(gòu)
    Thomassen與曲面嵌入圖的著色
    郯城县| 思茅市| 宁夏| 图片| 石柱| 册亨县| 烟台市| 长子县| 金川县| 枣庄市| 长春市| 临高县| 广元市| 尤溪县| 奇台县| 儋州市| 重庆市| 区。| 扎囊县| 辉南县| 雷波县| 永年县| 青神县| 布尔津县| 旌德县| 江口县| 兴义市| 汉川市| 雷山县| 双峰县| 常德市| 贵阳市| 嘉兴市| 六枝特区| 武乡县| 公主岭市| 吉安市| 新津县| 鲜城| 松江区| 浦北县|