葉 林 郭健紅

(臺州第一技師學(xué)院 浙江 溫嶺317500)

一類最大度為3的圖的L(2,1)-邊標(biāo)號的有效算法

葉 林 郭健紅

(臺州第一技師學(xué)院 浙江 溫嶺317500)

主要研究了一類其線圖最大度為3的圖的L(2,1)-邊標(biāo)號，給出了一個有效算法在線性時間之內(nèi)可以找到該類圖的9-L(2,1)-邊標(biāo)號，同時驗證了Griggs和Yeh猜想對于該圖類成立.

邊-L(2,1)-標(biāo)號;標(biāo)號數(shù);最大度;有效算法

0 引言

當(dāng)今世界,無線電頻率資源逐漸成為一種緊缺資源,頻率分配問題作為一個資源優(yōu)化配置問題擺到人們面前.頻率分配問題是對每個無線電發(fā)射臺分配一個頻率,使得相互干擾的無線電發(fā)射臺所分配的頻率的間隔在允許的范圍之內(nèi).關(guān)于頻率分配問題的研究已有數(shù)十年的歷史,Hale于1980年將此問題歸結(jié)成圖的T染色問題[1].

圖G的點集和邊集分別用V(G)和E(G)表示.對任意的v∈V(G),用dG(v)表示G中點v的度數(shù);分別用Δ和δ表示圖G的最大度和最小度.對任意的x,y∈V(G),dG(x,y)表示點x,y之間的距離.對任意的e1,e2∈E(G),dG(e1,e2)表示邊e1,e2之間的距離.一般地，我們簡單記為d(v)，d(x,y)和d(e1,e2).

孫學(xué)香[11]證明Δ(L(G))=3的簡單圖G，當(dāng)g(G)不長過7(其中g(shù)(G)是G的圍長)或者G存在奇圈時,λ′(G)≤8成立.

本文主要研究Δ(L(G))=3的簡單圖G,本文給出一個算法,可以在線性時間內(nèi)給出圖G的9-L(2,1)-邊標(biāo)號，從而證明λ′(G)≤9，驗證Griggs和Yeh猜想對于該類圖成立.

1 主要結(jié)論

定理1[12]設(shè)G是一個最大度為3的簡單圖,則G能被分解成2個邊不交的子集C和F.其中C表示點不交的圈集,F表示最大度不超過3的森林.

定理2 設(shè)G是一個滿足Δ(L(G))=3的簡單圖，則λ′(G)≤9.

證明 顯然G能被分解成如定理1所述的2個邊不交的子集C和F.令A(yù)={1,3,5,7},B={0,2,4,6,8}.

下面我們分別用A標(biāo)出F,B標(biāo)出C.

2 算法步驟

2.1 對F的邊標(biāo)號

標(biāo)號步驟1 取F內(nèi)的任何一棵未標(biāo)號樹T,取T內(nèi)的任何一點v0作為根點.根據(jù)T的邊與v0由近到遠的距離,取A中的最小有效數(shù)字對其一一標(biāo)號.

下面我們證明這一標(biāo)號方法的可行性.顯然,該標(biāo)號過程在O(|E(F)|)的時間內(nèi)可以完成.

因為G滿足Δ(G)=Δ(L(G))=3,所以G內(nèi)任何兩個最大度點,其距離至少為2.圖G內(nèi)同一個圈的兩條圈關(guān)聯(lián)邊至少間隔2條圈邊.因此來自不同樹的兩條邊,其距離至少為3.因此可以對F內(nèi)的樹各自標(biāo)號.

對于任何一棵樹T,我們斷言其邊能被A正常標(biāo)號.對|E(T)|進行歸納假設(shè).易見,若T僅是一條邊,則可用1進行標(biāo)號.假設(shè)|E(T)|=k(k≥2).取T內(nèi)離根點v0最遠的一片葉子w,記w的唯一鄰點為v,刪除邊vw.根據(jù)歸納假設(shè)可得,T-vw的邊能被A正常標(biāo)號.考慮到T內(nèi)的任何兩個最大度點,其距離至少為2.

(ⅰ)若dT(v)=3.則設(shè)v的另兩個非w鄰點為u,w′,其中dG(v0,w)=dG(v0,w′)≥dG(v0,u).易見,dT(u)≤2.若存在u的非v鄰點,則記為u′.考慮到用A中的元素給vw的標(biāo)號,則vw至多需避開uv,vw′以及uu′的標(biāo)號.則A中至少有|A|-3=1個數(shù)給以vw標(biāo)號.

(ⅱ)若dT(v)≤2.若存在v的非w鄰點,則記為u.易見dG(v)≤3,若存在u的兩個非v鄰點,則記為u′,u″.考慮到用A中的元素給vw的標(biāo)號,則vw至多需避開uv,uu′以及u′u″的標(biāo)號.則A中至少有|A|-3=1個數(shù)給以vw標(biāo)號.

因此,vw可以由A中的元素正常標(biāo)號.歸納假設(shè)成立.即T的邊能被A正常標(biāo)號.這樣,F的邊能被A正常標(biāo)號.

2.2 對C的邊標(biāo)號

設(shè)Ci是C的任何一個圈,設(shè)v是Ci內(nèi)的一個點.為方便起見,作如下定義:若dG(v)=2,則稱v是Ci的一個純點.若dG(v)=3,且與v關(guān)聯(lián)的樹邊被標(biāo)為a,則稱v是感染點,a是感染數(shù).稱數(shù)a-1和a+1對與v相關(guān)聯(lián)的兩條圈邊禁用.

易見,C內(nèi)的任何兩個圈,其距離至少是2,且任何圈都不含弦.取C的任一未標(biāo)號圈Ci,考慮Ci所含感染點的不同情況,按如下不同的方式,對Ci進行標(biāo)號.

情形1 存在Ci的一條邊,其含有兩個純點.

標(biāo)號步驟2 按同一方向,記Ci的邊為e1,e2,…，ei.標(biāo)e2為9,從e2開始,取B中的最小有效數(shù)字,依次給Ci上的邊標(biāo)號.

下面我們證明該標(biāo)號方法的可行性.

證明 由于Ci上的邊et(3≤t≤i)可能包含一個感染點,且et由B中的元素標(biāo)號.因此其至多要避開et-1和et-2的2個標(biāo)號,以及感染數(shù)在B內(nèi)的2個相鄰數(shù).因此至少有|B|-2-2=1個數(shù)可以標(biāo)給et.由于e1不包含任何感染點,因此其需避開數(shù)字8以及至多要避開ei,ei-1,e3的3個標(biāo)號.因此至少有|B|-1-3=1個數(shù)可以標(biāo)給e1.這樣,Ci能被標(biāo)號.

情形2 Ci的任何一條邊均包含一個感染點.

易見Ci的任何一條邊均包含一個純點和一個感染點,且Ci的階數(shù)是偶數(shù).

子情形2.1 存在連續(xù)的兩個感染點v1,v2,分別感染了不同的標(biāo)號a,b,不失一般性，設(shè)a

標(biāo)號步驟3 記兩條相鄰邊e1,e2，且v1∈e1,v2∈e2.按同一方向,記Ci的邊為e1,e2,…,ei.取B中的最小有效數(shù),其滿足對e1和ei禁用,但不對e2禁用.則將該數(shù)標(biāo)給e2.標(biāo)e3為9,從e4開始,取B中的最小有效數(shù)字,依次給Ci上的邊標(biāo)號.

下面我們證明該標(biāo)號方法的可行性.

證明 因為a≠b，則{a-1，a+1}≠{b-1，b+1}.由于a

子情形2.2 所有Ci的邊都感染了相同的數(shù).

設(shè)a,b,c,d是任意的4個標(biāo)號.記(abcd)表示abcd的循環(huán).

(ⅰ)若感染數(shù)為7

標(biāo)號步驟4 若|Ci|=4k,k∈N,則將Ci標(biāo)為(0249).若|Ci|=4k+2,k∈N,則將Ci標(biāo)為(0249)24.

(ⅱ)若感染數(shù)不為7

記a,b是兩個非感染數(shù)的相鄰數(shù),且a,b∈B{8}.用{a,b,8,9}標(biāo)Ci.

標(biāo)號步驟5 若|Ci|=4k,k∈N,則將Ci標(biāo)為(a8b9).若|Ci|=4k+2,k∈N,則將Ci標(biāo)為8ab9(a8b9)ab.

顯然,該標(biāo)號過程需要O(|E(C)|)的時間.從而對圖G的所有邊進行標(biāo)號需要O(|E(G)|)的時間.

如上所述,我們能在線性時間內(nèi)用{0,1,…,8,9}對G的邊進行標(biāo)號.且對于滿足Δ(G)=Δ(L(G))=3的簡單圖G,有λ′(G)≤9,Griggs和Yeh猜想成立.

[1]HALEWK.Frequencyassignment:theoryandapplication[J].ProcIEEE,1980,68:1497-1514.

[2]GRIGGS J R,YEH R K.Labelling graphs with a condition at distance 2[J].SIAM J Discrete Math，1992,5:586-595.

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

[5]CALAMONERIT.L(h,k)-labelingproblem:a survey and annotated bibliography[J].Comput J,2011,54:1344-1371.

[6]CHANG Feihuang, CHIA MaLian.L(2,1)-labelings of subdivisions of graphs[J].Discrete Math,2015,338:248-255.

[7]CHEN Qin,LIN Wensong.L(j,k)-labelings andL(j,k)-edge-labelings of graphs[J].Ars Combin, 2012,16:161-172.

[8]LIN Wensong,WU Jianzhuan.Distance two edge labelings of lattices[J].J Comb Optim,2013,25:661-679.

[9]HE Dan,LIN Wensong.OnL(1,2)-edge-labelings of some special classes of graphs[J].數(shù)學(xué)研究及應(yīng)用(英文版),2014,34(4):403-413.

[10]SETHURAMAN G,VELANKANNI A.(2,1)-Total Labeling of a Class of Subcubic Graphs[J].Electronic Notes in Discrete Mathematices，2015,48:259-266.

[11]孫學(xué)香.圖的距離2邊標(biāo)號數(shù)的上界[D].南京:東南大學(xué)應(yīng)用數(shù)學(xué)系,2007.

[12]SKULRATTANAKULCHAI San.4-edge-coloring graphs of maximum degree 3 in linear time[J].Information Processing Letters, 2002,81:191-195.

(責(zé)任編輯 鄧 穎)

An Efficient Algorithm forL(2,1)-edGe-labelling of Graphs with Maximum Degree 3

Ye Lin Guo Jianhong

(Taizhou No. 1 Technician College, Wenlin, Zhejiang 317500)

In this paper, we consider theL(2,1)-edGe-labelling of a class of graphs of maximum degree three. We present a linear algorithm to find a 9-L(2,1)-edGe-labelling and verify the correctness of the conjecture of Griggs and Yeh for the graph class considered.

edGe-L(2, 1)-labelling; labelling number; maximum degree; efficient algorithm

2016-09-18

葉 林(1984- ),女,浙江溫嶺人,講師,研究方向:圖論.

10.16169/j.issn.1008-293x.k.2016.09.07

O157.5

A

1008-293X(2016)09-0033-03