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

        ?

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

        2017-09-21 07:03:10董曉媛馬登舉
        關(guān)鍵詞:豎線拓?fù)鋱D標(biāo)號

        董曉媛,馬登舉

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

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

        董曉媛1,馬登舉2

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

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

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

        1 預(yù)備知識

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

        一個圖G的L(3,2,1)-標(biāo)號是從圖G的頂點(diǎn)集到非負(fù)整數(shù)集的一個映射f:V(G)→{0,1,2,…},使得對任意的兩個頂點(diǎn)u,v,|f(u)-f(v)|≥4-dist(u,v),這里dist(u,v)表示u,v之間的距離.圖G的L(3,2,1)-標(biāo)號數(shù)是指最小的數(shù)k,使得G有一個k-L(3,2,1)-標(biāo)號.圖G的L(3,2,1)-標(biāo)號數(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)-標(biāo)號進(jìn)行研究.

        圖1 Goldberg snark圖B3的一個畫法

        圖2 的一個畫法

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

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

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

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

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

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

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

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

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

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

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

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

        圖7 圖H

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

        由以上4個引理可知:

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

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

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

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

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

        證明因?yàn)镠是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)-標(biāo)號[J].高校應(yīng)用數(shù)學(xué)學(xué)報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.

        (責(zé)任編輯:李亞軍)

        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

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

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

        O 157.5 [學(xué)科代碼] 110·7470

        A

        猜你喜歡
        豎線拓?fù)鋱D標(biāo)號
        低壓配網(wǎng)拓?fù)鋱D自動成圖關(guān)鍵技術(shù)的研究與設(shè)計
        簡單拓?fù)鋱D及幾乎交錯鏈環(huán)補(bǔ)中的閉曲面
        可自動消除NG豎線缺陷的Mura檢測機(jī)設(shè)計探究
        基于含圈非連通圖優(yōu)美性的拓?fù)鋱D密碼
        TFT-LCD彩膜工藝宏觀缺陷自動化修補(bǔ)的探究
        非連通圖2D3,4∪G的優(yōu)美標(biāo)號
        象形文字走走看
        象形文字走走看
        非連通圖D3,4∪G的優(yōu)美標(biāo)號
        非連通圖(P1∨Pm)∪C4n∪P2的優(yōu)美性
        国产av无码专区亚洲av| 久久精品熟女亚洲av麻| 免费a级毛片无码a∨中文字幕下载 | 毛多水多www偷窥小便| 青春草国产视频| 国产精品久久国产精品久久 | 国内人妖一区二区在线播放| 国产一级一片内射视频播放| 色欲色欲天天天www亚洲伊| 日韩中文字幕欧美亚洲第一区| 久久国产高潮流白浆免费观看 | 人人做人人妻人人精| 国产精品亚洲专区无码不卡| 国产一区二区三免费视频| 国产成人亚洲综合无码品善网| 国产精品国语对白露脸在线播放| 在线观看极品裸体淫片av| 亚洲不卡一区二区视频| 天天躁日日躁狠狠躁欧美老妇| 国产羞羞视频在线观看| 用力草我小逼视频在线播放| 国产一区亚洲二区三区| 高清偷自拍第1页| 欧美色资源| h视频在线免费观看视频| 亚洲乳大丰满中文字幕| 欧美老妇人与禽交| 视频网站在线观看不卡| 久久久亚洲熟妇熟女av| 无码午夜成人1000部免费视频| 久久中文字幕日韩无码视频| 国产高清在线精品一区二区三区| 亚洲欧洲国产成人综合在线| 亚洲一区二区三区偷拍女厕 | 最新69国产精品视频| 国产女主播白浆在线观看| 一级二级中文字幕在线视频| 黄色大片国产精品久久| 欧美国产亚洲日韩在线二区| 亚洲av成人精品日韩一区| 亚洲av精品一区二区三|