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

        ?

        一類3-正則圖的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色

        2010-11-02 03:19:59楊隨義王治文
        關(guān)鍵詞:鄰點(diǎn)全色正則

        楊隨義,王治文

        一類3-正則圖的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色

        楊隨義1,王治文2

        (1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,甘肅天水741000; 2.寧夏大學(xué)數(shù)學(xué)計(jì)算機(jī)學(xué)院,寧夏銀川750021)

        對(duì)簡(jiǎn)單圖G(V,E),f是從V(G)∪E(G)到{1,2,…,k}的映射,k是自然數(shù),若f滿足(1)?uv∈E(G),u≠v,f(u)≠f(v);(2)?uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)?uv∈E(G),C(u)≠C(v);其中C(u)={f(u)}∪{f(uv)|uv∈E(G)};則稱f是G的一個(gè)關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色.給出了一類3-正則重圈圖Re(n,m)(m≥2,n≥3且n≡0(mod2))的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全色數(shù).

        3-正則重圈圖;鄰點(diǎn)可區(qū)別全染色;關(guān)聯(lián)鄰點(diǎn)可區(qū)別全色數(shù)

        圖的染色是圖論的重要研究?jī)?nèi)容之一,由計(jì)算機(jī)科學(xué)和信息科學(xué)等所產(chǎn)生的一般點(diǎn)可區(qū)別邊染色[1],鄰點(diǎn)可區(qū)別邊染色(或鄰強(qiáng)邊染色)[2-5]及D(β)點(diǎn)可區(qū)別邊染色[6],點(diǎn)可區(qū)別邊染色[7-8],鄰點(diǎn)可區(qū)別全染色[9]等都是十分困難的問(wèn)題,至今文獻(xiàn)甚少.在此基礎(chǔ)之上,Zhang進(jìn)一步提出了新的染色概念,圖的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色是其中之一[9].本文給出了一類3-正則重圈圖Re(n,m)(m≥2,n≥3且n≡0(mod2))的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全色數(shù).

        定義1[9]對(duì)于階數(shù)不小于2的連通圖G(V,E),f是從V(G)∪E(G)到{1,2,…,k}的映射,k是自然數(shù),如果f滿足:

        (1)?uv∈E(G),u≠v,有f(u)≠f(v);

        (2)?uv,uw∈E(G),v≠w,f(uv)≠f(uw);

        (3)?uv∈E(G),C(u)≠C(v);

        其中C(u)={f(u)}∪{f(uv)|uv∈E(G)};則稱f是圖G的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色,也稱G有k-關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色.(簡(jiǎn)記作k-I-AVD TC),記為G的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全色數(shù).

        定義2[10]設(shè)G(V,E)是簡(jiǎn)單圖,如果m≥2,n≥3且

        猜想1[9]對(duì)簡(jiǎn)單圖G,則有χiat(G)≤Δ+2,其中Δ是G的最大度.

        文中未加說(shuō)明的術(shù)語(yǔ)、記號(hào)可參看文獻(xiàn)[11,12].

        1 主要結(jié)論

        定理 對(duì)于3-正則重圈圖Re(n,m)(m≥2,n≥3且n≡0(mod2)),則有

        證明 由定義1知,χiat(Re(n,m))≥4,為證明χiat(Re(n,m))=4,僅需給出3-正則重圈圖Re(n,m)的一個(gè)4-I-AVD TC.如下定義一個(gè)從V(Re(n,m))∪E(Re(n,m))到{1,2,3,4}的映射f:

        情況1 若m=2,3時(shí),易證χiat(Re(n,m))=4(n≥3且n≡0(mod2))成立.

        情況2 當(dāng)m≥4時(shí),

        在下述證明中當(dāng)j+1>2n時(shí)j+1(mod2n).由于各層分布與m的值有關(guān),所以按m進(jìn)行如下分類:情況2.1當(dāng)m≡0(mod4)時(shí),

        情況2.2 當(dāng)m≡3(mod4)時(shí),

        此時(shí)

        情況2.3 當(dāng)m≡1(mod4)或m≡2(mod4)時(shí),類似于情況2.1,2.2證明.

        綜上可知,f是3-正則重圈圖Re(n,m)(m≥2,n≥3且n≡0(mod2))的一個(gè)4-I-AVD TC.

        [1] BURRIS A C,SCHELP R H.Vertex-distinguishing Proper Edge-coloring[J].J Graph Theory,1997,26(2):73-82.

        [2] BALISTER P N,GYORI E,L EHEL J,et al.Adjacent Vertex Distinguishing Edge-colorings[J].S IA MJ Discrete Math, 2007,21:237-250.

        [3] HATAMI H.Δ+300 is a Bound on the Adjacent Vertex Distinguishing Edge Chromatic Number[J].J ournal of Combinatorial Theory,SeriesB,2005,95:246-256.

        [4] ZHANG Z,LIU L,WANGJ.Adjacent Strong Edge Coloring of Graphs[J].A ppl Math Lett,2002,15:623-626.

        [5] ZHANG Zhong-fu,LI J,CHEN X,et al.D(β)-vertex-distinguishing Proper Edge-coloring of Graphs[J].Acta Math Sinica(Chin Ser),2006,15:703-708.

        [6] ZHANG Z,QIU P,XU B,et al.Vertex-distinguishing Total Coloring of Graphs[J].A rs Comb,2008,87:33-45.

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

        [8] ZHANG Z,CHEN X,LI J,et al.On Adjacent-vertex-distinguishing Total Coloring of Graphs[J].Sci Chins(S ER A), 2005,48(3):289-299.

        [9] CHANG C(ZHANG Z),WOODALL D R.LIJ,et al.Incidence Adjacent Vertex-distinguishing Total Coloring of Graphs

        [R].蘭州交通大學(xué)科學(xué)報(bào)告,2008,2:1-8.

        [10] ZHANG Z.The Smarandachely Adjacent Vertex Total Coloring of Graphs[R].蘭州交通大學(xué)科學(xué)報(bào)告,2009,2-3.

        [11] BONDYJ A,MURTY U S R.Graph Theory with Applications[M].London:Macmillan;New York:Elsever,1986.

        [12] 王治文,徐保根,閆麗宏,等.關(guān)于圈的廣義Mycielski圖的全染色[J].山西大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,31(4):20-23.

        Incidence Adjacent Vertex-distinguishing Total Coloring of a Kind of 3-regular Graph

        YANG Sui-yi1,WANG Zhi-wen2
        (1.College of Mathematics,Tianshui Normal University,Tianshui741000,China; 2.School of Mathematics and Computer Science,Ningxia University,Yinchuan750021,China)

        LetGbe a simple graph andkbe a positive integer.Iffis a mapping fromV(G)∪E(G)to{1,2,…,k},such that(1)?uv∈E(G),u≠v,f(u)≠f(v);(2)?uv,vw∈E(G),u≠w,f(uv)≠f(vw);(3)?uv∈E(G),C(u)≠C(v),we say thatfis a incidence adjacent vertex-distinguishing total coloring ofG,where C(u)={f(u)}∪{f(uv)|uv∈E(G)}.The minimal number ofkis called as the incidence adjacent vertexdistinguishing total chromatic number ofG.The incidence adjacent vertex-distinguishing total chromatic number of 3-repeated cycle graph is disussed.

        3-repeated cycle graph;incidence adjacent vertex-distinguishing total coloring;incidence adjacent vertex-distinguishing total chromatic number

        O157.5

        A

        0253-2395(2010)03-0354-04

        2009-11-01

        國(guó)家自然科學(xué)基金(10771091);寧夏大學(xué)科學(xué)研究基金((E)ndzr09-15)

        楊隨義(1977-),男,講師,主要從事代數(shù)圖論的研究.通訊作者王治文,E-mail:w.zhiwen@163.com

        猜你喜歡
        鄰點(diǎn)全色正則
        三星“享映時(shí)光 投已所好”4K全色激光絢幕品鑒會(huì)成功舉辦
        圍長(zhǎng)為5的3-正則有向圖的不交圈
        海信發(fā)布100英寸影院級(jí)全色激光電視
        淺談書(shū)畫裝裱修復(fù)中的全色技法
        收藏界(2019年4期)2019-10-14 00:31:10
        剩余有限Minimax可解群的4階正則自同構(gòu)
        類似于VNL環(huán)的環(huán)
        特殊圖的一般鄰點(diǎn)可區(qū)別全染色
        有限秩的可解群的正則自同構(gòu)
        全色影像、多光譜影像和融合影像的區(qū)別
        太空探索(2014年11期)2014-07-12 15:16:52
        笛卡爾積圖Pm×Kn及Cm×Kn的鄰點(diǎn)可區(qū)別E-全染色研究
        麻豆╳╳╳乱女另类| 黄页免费人成网址大全| 一区二区三区午夜视频在线| 欧美猛少妇色xxxxx猛交| 成人无码区免费a片www| 激情中文丁香激情综合| 口爆吞精美臀国产在线| 脱了老师内裤猛烈进入| 野花社区视频www官网| 色狠狠一区二区三区香蕉蜜桃| 亚洲日本精品一区二区三区| 精品欧美一区二区三区久久久| 无套内射无矿码免费看黄| 亚洲爆乳大丰满无码专区| 久久网站在线免费观看| 天堂网站一区二区三区| 99香蕉国产精品偷在线观看| av无码天堂一区二区三区| 国产av一区二区制服丝袜美腿| 亚洲欧美综合精品成人网站| 欧美老妇与zozoz0交| 亚洲AV无码一区二区三区精神| 91精品国产91综合久久蜜臀 | 久久精品国波多野结衣| 青青自拍视频成人免费观看| 精品综合一区二区三区| 无码精品日韩中文字幕| 91超碰在线观看免费| 久久成人永久婷婷99精品| 好紧好爽免费午夜视频| 美女裸体自慰在线观看| 99熟妇人妻精品一区五一看片| 二区三区三区视频在线观看| 双腿张开被9个男人调教| 久久综合视频网站| 亚州中文字幕乱码中文字幕| 人妻精品久久久久中文字幕69| 草草网站影院白丝内射| 色婷婷久久99综合精品jk白丝| 精品人妻码一区二区三区剧情| 免费观看黄网站在线播放|