• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      關于圖的鄰點可區(qū)別全色數(shù)的上界研究

      2012-07-05 14:32:48劉利群陳祥恩
      關鍵詞:鄰點上界全色

      劉利群,陳祥恩

      (1.長江大學信息與數(shù)學學院,湖北 荊州 434023;2.西北師范大學數(shù)學與信息科學學院,甘肅 蘭州 730079)

      關于圖的鄰點可區(qū)別全色數(shù)的上界研究

      劉利群1,陳祥恩2

      (1.長江大學信息與數(shù)學學院,湖北 荊州 434023;2.西北師范大學數(shù)學與信息科學學院,甘肅 蘭州 730079)

      圖G的鄰點可區(qū)別全染色是指G存在一個正常全染色f使得任意相鄰兩點有不同的色集合.本文主要研究鄰點可區(qū)別正常全色數(shù)的上界,目前鄰點可區(qū)別全染色的一個較好的上界是?+C+20,本文用概率方法改進了這個結(jié)果,得到了鄰點可區(qū)別全色數(shù)的一個較小上界?+C+3.

      鄰點可區(qū)別全染色;鄰點可區(qū)別全色數(shù);上界

      1 引言

      染色問題是圖論中具有重要實際意義和理論意義的研究課題之一.1965年,Bahzad和Vizing各自獨立提出了圖的全染色的概念和猜想.2004年,文獻[1-2]提出了圖的鄰點可區(qū)別全染色的概念和猜想.文獻[3-4]對圖的全染色作了進一步研究,得到了一些較好的結(jié)果.文獻[5]得到了鄰點可區(qū)別全染色的一個上界?+C+20.本文嘗試通過應用局部引理,得到了鄰點可區(qū)別全色數(shù)的一個較小的上界?+C+3.

      下面給出將要用到的一些概念與定理.

      定義1[1]G(V,E)是階至少為2的連通圖,k是正整數(shù),f是從V(G)∪E(G)到{1,2,···,k}的一個映射.對任意u∈V(G),記

      2 主要結(jié)果及證明

      定理1 設G(V,E)是連通圖,若

      證明 假設圖G(V,E)已給出,分以下四個步驟對圖G的邊進行染色:

      第一步由引理3,可先用?(G)+C種顏色對G進行正常全染色.

      第二步取一種新顏色a,對G的每個頂點隨機獨立的挑選它的一條關聯(lián)邊用新顏色a重染.這時,邊e=uv被新顏色a重染的概率是

      第三步在第二步完成后,另取一種新顏色b,再對G的每個頂點隨機獨立的挑選它的一條關聯(lián)邊用新顏色b重染.注意:新顏色b可能覆蓋新顏色a.

      第四步在第三步完成后,另取一種新顏色c,再對G的每個頂點隨機獨立的挑選它的一條關聯(lián)邊用新顏色c重染.注意:新顏色c可能覆蓋新顏色a,b.

      下面將證明以下兩點成立的概率為正:

      1.著色仍然正常即沒有相鄰兩條邊或相鄰的兩點著色相同或相關聯(lián)的點與邊著色相同;

      2.著色是鄰點可區(qū)別的即對任意兩點u,v∈V(G)(1≤d(u,v)≤2),有C(u)?=C(v).為此,定義如下壞事件:

      (I)對每對相鄰的邊{e,f∈E(G)},令Ae,f表示e和f被染成同種顏色的事件.

      (II)對每一條邊

      令Bu,v表示u和v的關聯(lián)邊是正常著色且C(u)=C(v)的事件.

      下面證明上述事件都不發(fā)生的概率為正.

      構(gòu)造相關圖D,其中D的頂點是以上二種類型的所有事件,設EX,EY是D的兩個頂點(每個X,Y是一對相鄰邊,或者是和一條邊相鄰的所有邊及其這條邊本身.EX和EY是相鄰的當且僅當X和Y至少包含一條公共邊.由于EX的每個事件發(fā)生依賴于X的邊,從而D是事件的相關圖.

      首先,需要計算每個壞事件發(fā)生的概率,有以下三條成立:

      1)對類型(I)的每個事件Ae,f,有

      [1]張忠輔,陳祥恩,李敬文,等.關于圖的鄰點可區(qū)別全染色[J].中國科學:A輯,2004,34(5):577-583.

      [2]Zhang Zhongfu,Chen X iang′en,Li Jingwen,et al.On the ad jacent vertex distinguishing total coloring of graph[J].Science in China:Ser A,2005,48(3):289-299.

      [3]Zhang Zhongfu,Yao Bing.A note on the ad jacent vertex distinguishing total chromatic number of graph[J]. Journal of Lanzhou Jiaotong University:Natural Science,2006,23(6):143-145.

      [4]M olloy M,Reed B.A bound on the total chromatic number[J].Combinatorica,1998,18:241-280.

      [5]晁福剛,張忠輔,強會英.圖的鄰點可區(qū)別全色數(shù)的一個上界[J].純粹數(shù)學與應用數(shù)學,2010,26(1):91-95.

      [6]A lon N,Spencer J.The Probabilistic Method[M].New York:W iley,1992.

      [7]M olloy M,Reed B.G raph Coloring and the Probabilistic M ethod[M].New York:Springer,2002.

      [8]Yap H P.Total Coloring of G raphs[M].New York:Springer,1996.

      [9]Bondy J A,M urty U SR.G raph Theory with App lications[M].London:London M acm illan Press,1976.

      [10]Dietel R.G raph Theory[M].New York:Springer,1997.

      On an upper bound for ad jacen t vertex d istinguish ing total ch rom atic num ber of graphs

      Liu Liqun1,Chen Xiang′en2

      (1.College of In form ation and M athem atics,Yangtze University,Jingzhou 434023,China; 2.College of M athem atics and In form ation Science,Northwest Norm al University,Lanzhou 730079,China)

      A proper total coloring of the graph G is called ad jacent vertex distinguishing total coloring,for any two ad jacent vertices u,v∈V(G),we have C(u)?=C(v),where C(u)is called color set of vertex u.Inthis paper, we study the upper bound on the ad jacent vertex distinguishing total chromatic number.Δ+C+20is a good conclusion of the upper bound on the ad jacent vertex distinguishing total chrom atic number of graphs up till now.By probability m ethod,we obtained the conclusion that a upper bound on the ad jacent vertex distinguishing total chrom atic number isΔ+C+3 in som e condition in this paper.

      ad jacent vertex distinguishing total coloring,ad jacent vertex distinguishing total chrom atic number,upper bound

      O157.5

      A

      1008-5513(2012)06-0744-05

      2011-12-16.

      國家自然科學基金(61163037,61163054).

      劉利群(1977-),碩士,講師,研究方向:圖論及其應用.

      2010 M SC:05C15

      猜你喜歡
      鄰點上界全色
      三星“享映時光 投已所好”4K全色激光絢幕品鑒會成功舉辦
      圍長為5的3-正則有向圖的不交圈
      海信發(fā)布100英寸影院級全色激光電視
      淺談書畫裝裱修復中的全色技法
      收藏界(2019年4期)2019-10-14 00:31:10
      一個三角形角平分線不等式的上界估計
      一道經(jīng)典不等式的再加強
      特殊圖的一般鄰點可區(qū)別全染色
      Nekrasov矩陣‖A-1‖∞的上界估計
      全色影像、多光譜影像和融合影像的區(qū)別
      太空探索(2014年11期)2014-07-12 15:16:52
      笛卡爾積圖Pm×Kn及Cm×Kn的鄰點可區(qū)別E-全染色研究
      喀什市| 新宁县| 金阳县| 皮山县| 从化市| 玉龙| 姜堰市| 泉州市| 石屏县| 平邑县| 汨罗市| 广德县| 彝良县| 新民市| 柯坪县| 常德市| 长垣县| 休宁县| 璧山县| 黄大仙区| 绍兴县| 大冶市| 穆棱市| 龙泉市| 鄄城县| 呼玛县| 高淳县| 六安市| 平阴县| 夹江县| 岚皋县| 华阴市| 若尔盖县| 水富县| 东乡| 永胜县| 温宿县| 海林市| 万年县| 东辽县| 安泽县|