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

        ?

        Goldberg snark圖的L(3,2,1)-標號

        2017-09-21 07:03:10董曉媛馬登舉
        東北師大學報(自然科學版) 2017年3期
        關鍵詞:豎線拓撲圖標號

        董曉媛,馬登舉

        (1.南通師范高等??茖W校數(shù)理系,江蘇 南通 226000; 2.南通大學理學院,江蘇 南通 226007)

        Goldberg snark圖的L(3,2,1)-標號

        董曉媛1,馬登舉2

        (1.南通師范高等??茖W校數(shù)理系,江蘇 南通 226000; 2.南通大學理學院,江蘇 南通 226007)

        討論了Goldberg snark圖的L(3,2,1)-標號問題,給出了Goldberg snark圖Bk的L(3,2,1)-標號數(shù)的界,即11≤λ3,2,1(Bk)≤16.

        L(3,2,1)-標號;Goldberg snark圖;標號問題

        1 預備知識

        頻率分配問題是對每個無線電臺分配一個頻率,使得相互干擾的無線電發(fā)射臺所分配的頻率間隔在允許的范圍之內.Hale[1]于1980年將此問題歸結為圖的T-染色問題.Roberts于1990年研究了幾個不同地點的無線電發(fā)射臺如何有效分配無線電頻率問題:將頻率用非負整數(shù)表示,從而相近的地點分配不同的頻率,且極相近的地點分配的頻率至少相差2,這樣使得這些頻率不會相互干擾.Chang等[2]于1996年更精確地提出了圖G的L(2,1)-標號問題.圖的L(3,2,1)-標號是圖的L(2,1)-標號的一個推廣.

        一個圖G的L(3,2,1)-標號是從圖G的頂點集到非負整數(shù)集的一個映射f:V(G)→{0,1,2,…},使得對任意的兩個頂點u,v,|f(u)-f(v)|≥4-dist(u,v),這里dist(u,v)表示u,v之間的距離.圖G的L(3,2,1)-標號數(shù)是指最小的數(shù)k,使得G有一個k-L(3,2,1)-標號.圖G的L(3,2,1)-標號數(shù)用λ3,2,1(G)表示.翟明清等[3]在2007年得到:對有最大度為Δ的任意圖G,λ3,2,1(G)≤Δ3+2Δ.

        若一個3正則圖是二邊連通且不可3-邊著色的,同時圍長至少為5,也無非平凡3-邊割集,則稱之為snark圖.Petersen圖是最小的snark圖,自1975年以來,更多的snark圖被研究人員發(fā)現(xiàn).本文對Goldberg snark圖的L(3,2,1)-標號進行研究.

        圖1 Goldberg snark圖B3的一個畫法

        圖2 的一個畫法

        2 主要結論及證明

        為了研究Goldberg snark圖的L(3,2,1)-標號數(shù),首先研究Goldberg圖Bk的L(3,2,1)-標號數(shù).

        引理1 當k≡0(mod 4)時,有λ3,2,1(Bk)≤15.

        圖3 的一個L(3,2,1)-標號(豎線前即為)

        引理2 當k≡1(mod 4)時,有λ3,2,1(Bk)≤16.

        圖4 的一個L(3,2,1)-標號(豎線前面首位相連就是)

        同理可以驗證這是一個L(3,2,1)-標號,從而λ3,2,1(Bk)≤16.

        引理3 當k≡2(mod 4)時,λ3,2,1(Bk)≤16.

        圖5 的一個L(3,2,1)-標號(豎線前面首位相連就是)

        同理可以驗證這是一個L(3,2,1)-標號,從而λ3,2,1(B4m+2)≤16.

        引理4 當k≡3(mod 4)時,λ3,2,1(Bk)≤16.

        圖6 的一個L(3,2,1)-標號(豎線前面首位相連就是)

        圖7 圖H

        同理可以驗證這是一個L(3,2,1)-標號,故λ3,2,1(B4m+3)≤16.

        由以上4個引理可知:

        接下來給出λ3,2,1(Bk)的一個下界.

        引理5 設圖H如圖7所示,則λ3,2,1(H)≥11.

        假設λ3,2,1(H)≤10.設f是H的一個k-L(3,2,1)-標號,則k≤10.

        定理2 Goldberg snark圖Bk的L(3,2,1)-標號數(shù)λ3,2,1(Bk)滿足

        11≤λ3,2,1(Bk)≤16.

        證明因為H是Goldberg snark圖的一個子圖,所以λ3,2,1(Bk)≥11.再由定理1,λ3,2,1(Bk)≤16.因此11≤λ3,2,1(Bk)≤16.

        [1] HALE W K. Frequency assignment:theory and application [J]. Proc IEEE,1980,68:1497-1514.

        [2] CHANG G J,KUO D. TheL(2,1)-labeling on graphs [J]. SIAM J Discrete Math,1996(9):309-316.

        [3] 翟明清,董琳,呂長虹.圖的L(3,2,1)-標號[J].高校應用數(shù)學學報A輯,2007,22(2):240-246.

        [4] CHIA M L,KUO D,LIAO H,et al.L(3,2,1) labeling of graphs[J].Taiwan J Math,1992,15:2439-2457.

        [5] SHAO Z D,LIU J Z. TheL(3,2,1)-labeling problem on graphs[J].Math Appl,2004,17:596-602.

        [6] HAO R X,NIU J Z,WANG X F,et al. A note on Berge-Fulkerson coloring[J].Discrete Mathematics,2009,309:4235-4240.

        (責任編輯:李亞軍)

        TheL(3,2,1)-labelingofGoldbergsnarkgraphs

        DONG Xiao-yuan1,MA Deng-ju2

        (1.Department of Mathematics and Physics,Nantong Normal College,Nantong 226000,China: 2.School of Sciences,Nantong University,Nantong 226007,China)

        TheL(3,2,1)-labeling problem of a graph Goldberg snarkBkis considered. The bounds for theL(3,2,1)-labeling number of Goldberg snarkBkare given by 11≤λ3,2,1(Bk)≤16.

        L(3,2,1)-labeling;Goldberg snark graph;the labeling problem

        1000-1832(2017)03-0005-03

        10.16163/j.cnki.22-1123/n.2017.03.002

        2016-03-09

        國家自然科學基金資助項目(11171114,11371207);南通師范高等專科學校重點資助課題(TSGZ201606).

        董曉媛(1984—),女,碩士,講師,主要從事拓撲圖論研究;通信作者:馬登舉(1968—),男,博士,副教授,主要從事拓撲圖論研究.

        O 157.5 [學科代碼] 110·7470

        A

        猜你喜歡
        豎線拓撲圖標號
        低壓配網(wǎng)拓撲圖自動成圖關鍵技術的研究與設計
        簡單拓撲圖及幾乎交錯鏈環(huán)補中的閉曲面
        可自動消除NG豎線缺陷的Mura檢測機設計探究
        基于含圈非連通圖優(yōu)美性的拓撲圖密碼
        TFT-LCD彩膜工藝宏觀缺陷自動化修補的探究
        非連通圖2D3,4∪G的優(yōu)美標號
        象形文字走走看
        象形文字走走看
        非連通圖D3,4∪G的優(yōu)美標號
        非連通圖(P1∨Pm)∪C4n∪P2的優(yōu)美性
        日本高清人妻一区二区| 欧美午夜一区二区福利视频| 日韩AV有码无码一区二区三区| 亚洲精品尤物av在线网站| 国产精品国产自产自拍高清av| 人妻少妇精品视频三区二区一区| 欧美成人一区二区三区在线观看| 人妻无码ΑV中文字幕久久琪琪布 尤物AV无码色AV无码麻豆 | 少妇性饥渴无码a区免费| 国产乱子伦露脸在线| 青青草国内视频在线观看| 青青草高中生在线视频| 爆乳熟妇一区二区三区霸乳 | 成l人在线观看线路1| 欧美精品久久久久久久久| 免费啪啪av人妻一区二区| av熟妇一区二区三区| 久久综合国产乱子伦精品免费| 久久久久国产一级毛片高清版A | 久久精品国产精品亚洲艾| 国产爆乳无码一区二区麻豆| 精品人妻系列无码人妻免费视频| 国产九九在线观看播放| 亚洲禁区一区二区三区天美| 成人亚洲一区二区三区在线| 亚洲精品永久在线观看| 中文字幕人妻少妇美臀| 亚洲国产性夜夜综合另类 | 无码人妻久久一区二区三区免费丨 | 国产午夜视频一区二区三区| 日本精品αv中文字幕| 久久99久久久无码国产精品色戒| av有码在线一区二区三区| 欧洲熟妇色xxxx欧美老妇软件| 欧美日韩中文国产一区| 男人的天堂av一二三区| 喷水白浆视频在线观看| 免费中文熟妇在线影片| 亚洲精品中文字幕观看| 蜜乳一区二区三区亚洲国产| 人人妻人人狠人人爽天天综合网|