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

葉 林 郭健紅

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

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

葉 林 郭健紅

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

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

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

0 引言

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

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

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

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

1 主要結(jié)論

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

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

證明 顯然G能被分解成如定理1所述的2個(gè)邊不交的子集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 對(duì)F的邊標(biāo)號(hào)

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

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

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

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

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

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

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

2.2 對(duì)C的邊標(biāo)號(hào)

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

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

情形1 存在Ci的一條邊,其含有兩個(gè)純點(diǎn).

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

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

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

情形2 Ci的任何一條邊均包含一個(gè)感染點(diǎn).

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

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

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

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

證明 因?yàn)閍≠b，則{a-1，a+1}≠{b-1，b+1}.由于a

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

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

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

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

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

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

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

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

如上所述,我們能在線性時(shí)間內(nèi)用{0,1,…,8,9}對(duì)G的邊進(jìn)行標(biāo)號(hào).且對(duì)于滿足Δ(G)=Δ(L(G))=3的簡(jiǎn)單圖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)號(hà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