亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        廣義Mycielski圖的鄰點可區(qū)別的非正常全染色

        2010-03-22 20:45:39劉利群
        通化師范學院學報 2010年12期
        關鍵詞:利群鄰點全色

        劉利群

        (長江大學 信息與數(shù)學學院,湖北 荊州 434023)

        1 引言

        染色問題是圖論中具有重要實際意義和理論意義的研究課題之一.本文考慮的圖均為沒有孤立邊,最多有一個孤立點的有限無向單圖. 2004年,張忠輔和陳祥恩等人引入了圖的鄰點可區(qū)別的全染色的概念[1],許多學者對圖的鄰點可區(qū)別的全染色的理論作了大量的研究. 2005年,文獻[2]提出了圖的鄰點可區(qū)別非正常邊色數(shù)及全色數(shù)(一般鄰點可區(qū)別色指標)的概念(General neighbour-distinguishing index of a graph).另外,文中一些其他術語及符號參見文獻[3].

        下面給出一些相關概念:

        定義1[1]對階數(shù)至少為2的連通圖G(V,E),令f為從V(G)∪E(G)到{1,2,…,k}的映射,其中k為正整數(shù).對任意的u∈V(G),C(u)表示{f(u)∪f(uv|uv∈E(G))}.如果f滿足下面的條件

        1)對任意的uv,vw∈E(G),u≠v,有f(uv)≠f(vw),

        2)對任意的uv∈E(G),u≠v,有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)則稱f為圖G的一個k-正常全染色.如果f為圖G的一個k-正常全染色,并滿足

        3)對任意的uv∈E(G),有C(u)≠C(v),則稱f為圖G的一個k-鄰點可區(qū)別全染色(簡記為k=AVDTC).

        定義2[2]對圖G(V,E),映射F∶E(G)∪V(G)→{1,2,…,k}滿足對任意u,v∈V(G),uv∈E(G)有C(u)≠C(v),則稱f是G的鄰點可區(qū)別的非正常全染色或一般鄰點可區(qū)別全染色,簡記為gndt-染色.并稱gndti(G)=min{k|G有k-gndt-染色}為G的鄰點可區(qū)別的非正常全色數(shù)或一般鄰點可區(qū)別色指標(general neighbour-distinguishing index of a graph).

        定義3[4]設G是頂點集合為V(G)={v0i|i=1,2,…,p}的簡單圖,n是正整數(shù),稱Mn(G)為G上的錐(或廣義Mycielski圖),如果

        V(Mn(G))={v01,v02,…,v0p;v11,v12,…
        ,v1p,…,vn1,vn2,…,vnp,w},

        2 主要結果及證明

        證明 令V(Pm)={v01,v02,…,v0m},E(Pm)={v01v02,v02v03…,,v0(m-1)v0m},

        V(Mn(Pm)/{w})={v01,v02,…,v0m,
        v11,v12,…,v1m,…,vn1,…,vnm},

        若f(v01v02)=1,f(v02v03)=2,則f(v03v04)=2,f(v03v01)=2,則v01與v02的色集合相同,這與它們是鄰點可區(qū)別的相矛盾.其他染法類似可推出矛盾.

        g(vij)=1,i∈{0,1,…,n},j≡1(mod3);
        g(vij)=2,i∈{0,1,…,n},j≡3(mod3);
        g(vij)=3,i∈{0,1,…,n},j≡0(mod3);

        2)再重新給點染色,當g(u)=1時,令f(u)=2;當g(u)=2時,令f(u)=3;當g(u)=3時,令f(u)=1;

        證明 令V(Pm)={v01,v02,…,v0m},E(Pm)={v01v02,v02v03…,,v0(m-1)v0m},

        V(Mn(Pm)/{w})={v01,v02,…,v0m,
        v11,v12,…,v1m,…,vn1,…,vnm},

        當g(vni)=1時,令f(vniw)=2;當g(vni)=2時,令f(vniw)=3;當g(vni)=3時,令f(vniw)=1(i=1,2,…,m).

        頂點w可染其中任一顏色.

        參考文獻:

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

        [2]Grorie, Hornak M, Palmer C,et al.General neighbour-distinguishing index of a graph [J].Discrete Mathematics, Special Issue devoted to BBS,2005.

        [3] Bondy J A,Murty U S R. Graph Theory with Applications[M].London:Macmillan Press Ltd,1976.

        [4] Tardif C.Fraetional chromatic numbers of cones over graphs [J].Graph Theory, 2001,38:87-94.

        [5]Zhang Zhong-fu, Liu Lin-zhong, Wang Jian-fang. Adjacent Strong Edge Coloring of Graphs[J].Applied Mathematics Letters,2002,15(5).

        [6]劉利群,陳祥恩.路和圈上的錐的D(2)-點可區(qū)別正常邊染色[J].山東大學學報,2008,43(2):87-97.

        [7]Balister P N,Riordan O M,Schelp R H, Vertex-distinguishing edge colorings of graphs[J]. Graph Theory 42,2003,95-109.

        [8] Bazgan C,Harkat-Benhamdine A,Li Hao,et al, On the vertex-distinguishing edge colorings of graphs[J].J of Combin Theory,1999,75.

        [9]Balister P N, Bollobás B and Schelp R H, Vertex distinguishing colorings of graphs with△(G)=2 [J].Discrete Mathematics, 2002,252.

        猜你喜歡
        利群鄰點全色
        三星“享映時光 投已所好”4K全色激光絢幕品鑒會成功舉辦
        圍長為5的3-正則有向圖的不交圈
        海信發(fā)布100英寸影院級全色激光電視
        淺談書畫裝裱修復中的全色技法
        收藏界(2019年4期)2019-10-14 00:31:10
        來活力臺東,逛升級擴容版利群
        商周刊(2019年18期)2019-10-12 08:51:24
        利群:順勢而為,登場華東
        商周刊(2018年19期)2018-10-26 03:31:16
        走向“利群時代”
        商周刊(2018年17期)2018-08-31 02:20:12
        我的爸爸
        特殊圖的一般鄰點可區(qū)別全染色
        全色影像、多光譜影像和融合影像的區(qū)別
        太空探索(2014年11期)2014-07-12 15:16:52
        精品含羞草免费视频观看| 亚洲一区二区情侣| 亚洲天堂一二三四区在线| 黄片小视频免费观看完整版| 亚洲av片在线观看| 国内精品九九久久久精品| 99RE6在线观看国产精品| 丝袜av乱码字幕三级人妻| 人人妻人人澡人人爽国产一区| 狠狠色综合网站久久久久久久| 国产午夜精品久久久久99| 亚洲天堂线上免费av| 99久久无码一区人妻| 久久久久久人妻毛片a片| 国产精品亚洲片夜色在线| 免费黄网站永久地址进入| 色偷偷色噜噜狠狠网站30根 | 日本一区二区在线免费看 | 无码精品人妻一区二区三区人妻斩| 国产WW久久久久久久久久 | 亚洲国产精品成人av在线不卡| 亚洲国产av玩弄放荡人妇| 日韩A∨精品久久久久| 日本最新在线一区二区| 国内精品少妇高潮视频| 亚洲午夜无码av毛片久久| jjzz日本护士| 国产精品区二区东京在线| 亚洲欧美综合精品成人网站| 国产精品久久久久电影网| 亚欧同人精品天堂| 亚洲av第一区国产精品| 国产成人精品午夜视频| 国产91精品成人不卡在线观看| 成人偷拍自拍在线视频| 97色伦图片97综合影院| 国产精品美女久久久久久久久| 久久精品国产亚洲AV高清y w| 美艳善良的丝袜高跟美腿| 性欧美老人牲交xxxxx视频| 麻豆国产av尤物网站尤物|