国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

蛛形圖的D(3)-點(diǎn)可區(qū)別的全染色

2013-09-30 09:29:10張東翰
關(guān)鍵詞:用色全色條路

張東翰

(商洛學(xué)院數(shù)學(xué)與計(jì)算科學(xué)系,陜西商洛726000)

圖的染色是圖論中最著名和最古老的問(wèn)題之一,由于其應(yīng)用的廣泛性使得越來(lái)越多的學(xué)者對(duì)其進(jìn)行了研究.文獻(xiàn)[1-3]討論了圖的點(diǎn)可區(qū)別的邊染色,文獻(xiàn)[4]提出了圖的距離不大于β的任意2點(diǎn)可區(qū)別的邊染色并對(duì)一些特殊圖的色數(shù)進(jìn)行了探討,文獻(xiàn)[5]對(duì)特殊圖的3,4距離的邊染色做了一些研究,文獻(xiàn)[6-7]對(duì)圖的2距離點(diǎn)色數(shù)給予了討論,文獻(xiàn)[8-9]對(duì)特殊圖的全染色進(jìn)行了研究,文獻(xiàn)[10]提出了圖的距離不大于β的點(diǎn)可區(qū)別的全染色并對(duì)一些特殊圖的色數(shù)進(jìn)行了探討,對(duì)蛛形圖的色數(shù)的研究有一定的實(shí)際意義,文獻(xiàn)[11]討論了蛛形圖的若干染色問(wèn)題.圖的距離染色是圖染色研究的熱點(diǎn)之一,并已經(jīng)取得了很多重要的結(jié)果.筆者利用構(gòu)造具體染色的方法,確定了蛛形圖的距離不大于3的任意2點(diǎn)可區(qū)別的全色數(shù).

1 預(yù)備知識(shí)

定義1[10]設(shè) G(V,E)是簡(jiǎn)單圖,k 是正整數(shù),f是從 V(G)∪E(G)到 C={1,2,…,k}的映射,若

1)對(duì)任意的邊 uvE(G),有 f(u)≠f(v),f(v)≠f(uv)≠f(v),

2)對(duì)任意的2條相鄰的邊uv,uw E(G)(v≠w),有f(uv)≠f(uw),則稱(chēng)f是圖G的一個(gè)k-正常全染色(簡(jiǎn)記作k-PTC),且稱(chēng)數(shù)χT(G)=min{k|圖G存在k-PTC}為G的全色數(shù).

設(shè)β為正整數(shù),f是圖G的一個(gè)k-正常全染色,對(duì)任意的x V(G),讓C(x)表示在f下點(diǎn)x的顏色以及與x關(guān)聯(lián)的邊的顏色構(gòu)成的集合,稱(chēng)之為點(diǎn)x在f下的色集合.C(x)在全體k種顏色構(gòu)成的集合中的補(bǔ)集記為(x),若對(duì)任意的u,vV(G),且u 與v在G 中的距離dG(u,v)≤β,u≠v都有C(u)≠C(v),那么稱(chēng)f為圖G的一個(gè)k-D(β)-點(diǎn)可區(qū)別全染色(簡(jiǎn)記為k-D(β)-VDTC),并將χβ-vt(G)=min{k|G有一個(gè)k-D(β)-VDTC}稱(chēng)為圖G的D(β)點(diǎn)可區(qū)別全色數(shù).

定義2[11]蛛形圖Sk的頭點(diǎn)為v0,從v0出發(fā)有k(k≥3)條路,每條路的長(zhǎng)為k,共有n(n=k2+1)個(gè)點(diǎn),刪去v0后,得到的彼此不交的k條路分別記為Pi=vi1vi2…vik,(1≤i≤k),eij表示Pi中連接vi(j-1)和vij(1≤i≤k,2≤j≤k)的邊,連接 v0和 vi1的邊記為 ei1(1≤i≤k).

引理1[10]設(shè) G 是連通圖且|V(G)|≥3,則有(G),其中ni表示使任意2點(diǎn)間的距離不超過(guò)β的度為i的點(diǎn)的最大數(shù)目,δ和Δ分別表示圖G的最小度和最大度,θ是正整數(shù).

本文中未加述及的術(shù)語(yǔ)、記號(hào)可參考文獻(xiàn)[12-13].

2 定理及其證明

定理1 設(shè)Sk是蛛形圖,則有χ3-vt(Sk)=k+1.

證明 當(dāng)k=3時(shí),μ3=4,根據(jù)引理1可知χ3-vt(Sk)≥4,要證明χ3-vt(Sk)=4成立,只需給出一個(gè)4-D(3)-VDTC. 現(xiàn)給出一個(gè)4-D(3)-VDTC,使用的顏色為 1,2,3,4. 對(duì)于邊 v0v11,v11v12,v12v13分別用色 1,3,4染;對(duì)于邊 v0v21,v21v22,v22v23分別用色 2,4,1 染;對(duì)于邊 v0v31,v31v32,v32v33分別用色 3,4,1 染,對(duì)于點(diǎn) v0用色 4 染,對(duì)于點(diǎn) v11,v12,v13分別用色 2,1,2 染;對(duì)于點(diǎn) v21,v22,v23分別用色 1,3,2 染;對(duì)于點(diǎn) v31,v32,v33分別用色2,3,2染,則此染色是一個(gè)正常的全染色,又因?yàn)?/p>

可知對(duì)于距離不大于3的任意2點(diǎn)色集合不同,所以此染色為S3一個(gè)4-D(3)-VDTC,因此當(dāng)k=3時(shí)結(jié)論成立.

當(dāng)k≥4時(shí),μ3=k+1,根據(jù)引理1可知 χ3-vt(Sk)≥k+1,為了證明 χ3-vt(Sk)=k+1,只需給出一個(gè)Sk-(k+1)-D(3)-VDTC,使用的顏色為 1,2,…,k+1,對(duì)于邊 v0v11,v11v12,…,v1(k-1)v1k分別用色 1,2,3,4,5,…,k 染;對(duì)于邊 v0vi1,vi1vi2,…,vi(k-1)vik分別用色 i,i+1,…,k,1,2,…,i-1 染 i=2,3,…,k;對(duì)于點(diǎn) v0用色k+1 染;對(duì)于點(diǎn) v11,v12,…,v1(k-1),v1k分別用色 3,k+1,2,3,…,k-1 染;對(duì)于點(diǎn) v21,v22,…,v2(k-1),v2k分別用色 4,k+1,3,…,k 染;對(duì)于點(diǎn) v(k-1)1,v(k-1)2,…,v(k-1)(k-1),v(k-1)k分別用色 1,k+1,k,1,2,…,k-3 染;對(duì)于點(diǎn) vk1,vk2,…,vk(k-1),vkk分別用色 2,k+1,1,2,…,k-2 染;對(duì)于點(diǎn) vi1,vi2,…,vi(k-1),vik分別用色 i+2,k+1,i+1,i+2,…,k,1,2,…,i-2 來(lái)染 i=3,4,…,k-2,則此染色法為 Sk一個(gè)正常的全染色,又因?yàn)?/p>

且每條路Pi=vi1,vi2,…,vik,(1≤i≤k)上各個(gè)邊都染不同的顏色,所以在正常全染色下每條路上的任意2點(diǎn)的色集合不同.因此對(duì)于距離不大于3的任意2點(diǎn)其色集合不同,所以此染色為一個(gè)(k+1)-D(3)-VDTC.當(dāng)k≥4時(shí)結(jié)論成立.

綜上所述,定理1成立.

[1]BALISTER P N,HUANG Y Q,CHU Y M.Vertex-distinguishng edge colorings of graphs[J].J.of Graph Theory,2003,42:95-109.

[2]BAZGAN C,HARAT-BENHAMDIE A,LI H,et al.On the vertex-distinguishing proper edge-colorings of graphs[J].J.of Combin Theory,1999,75:288-301.

[3]BURRIS A C ,SCHELP R H.Vertex-distinguishing proper edge colorings[J].J.of Graph Theory,1977,26:73-82.

[4]張忠輔,李敬文,陳祥恩,等.圖的距離不大于β的任意兩點(diǎn)可區(qū)別的邊染色[J].數(shù)學(xué)學(xué)報(bào),2006,49(3):703-708.

[5]田京京.路和圈的距離不大于3和4的點(diǎn)可區(qū)別的邊染色[J].蘭州理工大學(xué)學(xué)報(bào),2008,34(4):156-158.

[6]于蘭蘭.單圈圖的2距離色數(shù)[J].甘肅科學(xué)學(xué)報(bào),2009,21(3):41-42.

[7]陳海鈺,劉信生.最大度為Δ圖類(lèi)的2距離色數(shù)的一個(gè)下界[J].甘肅科學(xué)學(xué)報(bào),2007,19(3):4-5.

[8]張東翰.路的廣義Mycielski圖的全染色[J].商洛學(xué)院學(xué)報(bào),2012,26(2):9-10.

[9]楊鵬輝.輪形圖的全著色[J].海南大學(xué)學(xué)報(bào):自然科學(xué)版,2011,29(1):8-10.

[10]張忠輔,李敬文,陳祥恩,等.圖的距離不大于β的點(diǎn)可區(qū)別的全染色[J].中國(guó)科學(xué):A輯,2006,36(10):1119-1130.

[11]孫亮萍,強(qiáng)會(huì)英,孟利冬.蛛形圖的若干染色問(wèn)題[J].蘭州交通大學(xué)學(xué)報(bào),2011,30(4):41-42.

[12]BONDY J A,MURTY U S R.Graph Theory with Applications[M].New York:Elsevier Science Publishing Co.,1976.

[13]REINHARD D.Graph Theory[M].New York:Springer-Verlag,1997.

猜你喜歡
用色全色條路
這條路
三星“享映時(shí)光 投已所好”4K全色激光絢幕品鑒會(huì)成功舉辦
海信發(fā)布100英寸影院級(jí)全色激光電視
淺談書(shū)畫(huà)裝裱修復(fù)中的全色技法
收藏界(2019年4期)2019-10-14 00:31:10
淺析蘇州博物館新館的建筑特點(diǎn)
祖國(guó)(2019年1期)2019-02-22 02:05:08
“墨點(diǎn)無(wú)多淚點(diǎn)多”
這條路
心聲歌刊(2018年6期)2018-01-24 00:56:12
平面設(shè)計(jì)中用色要素探究
大觀(guān)(2016年6期)2016-07-05 09:21:56
多點(diǎn)執(zhí)業(yè)這條路還沒(méi)有修好
這條路
抚宁县| 长丰县| 资中县| 青海省| 石家庄市| 永清县| 大方县| 太康县| 南和县| 宁乡县| 庄浪县| 扎鲁特旗| 保康县| 贵德县| 新闻| 旬阳县| 西藏| 兰坪| 岳普湖县| 江西省| 诸暨市| 辉县市| 闽清县| 根河市| 于田县| 彝良县| 莱西市| 栾城县| 德令哈市| 洪雅县| 瑞安市| 大名县| 邵武市| 府谷县| 漳平市| 定安县| 吉木萨尔县| 四会市| 大冶市| 寿光市| 文成县|