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

葉 林 李 涌

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

1 基礎(chǔ)知識(shí)

圖G的一個(gè)L(2,1)-標(biāo)號(hào)問(wèn)題來(lái)自于無(wú)線電的頻率分配問(wèn)題[1-2].本文中G的點(diǎn)集和邊集分別用V(G)和E(G)表示.對(duì)任意的v∈V(G),用d(v)表示G中點(diǎn)v的度數(shù)；對(duì)任意的x,y∈V(G),d(x,y)表示點(diǎn)x,y之間的距離.對(duì)任意的e1,e2∈E(G),d(e1,e2)表示邊e1,e2之間的距離.

令f:V(G)→{0,1,2,3,…}為一個(gè)映射,若對(duì)任意的x,y∈V(G),滿足當(dāng)d(x,y)=1時(shí),有|f(x)-f(y)|≥2.當(dāng)d(x,y)=2時(shí),|f(x)-f(y)|≥1,則稱(chēng)f為G的一個(gè)L(2,1)-標(biāo)號(hào).圖G的L(2,1)-標(biāo)號(hào)數(shù)λ(G)是指最小的正整數(shù)k使得G有一個(gè)L(2,1)-標(biāo)號(hào)f滿足f(V)?{0,1,2,…k}.Griggs和Yeh[2]證明了對(duì)最大度Δ≥1的圖G有λ(G)≤Δ2+2Δ. 此外, 他們還猜想對(duì)于任何Δ(G)≥2的圖,有λ(G)≤Δ2.并證明對(duì)于一些特殊圖,如路,2,樹(shù)以及直徑為2的圖時(shí),該猜想成立.關(guān)于這類(lèi)問(wèn)題的研究,參考文獻(xiàn)[2-4].

類(lèi)似地,給定圖G的一個(gè)L(2,1)-邊標(biāo)號(hào)是從圖G的邊集到非負(fù)整數(shù)集的一個(gè)映射f滿足：對(duì)任意的e1,e2∈E(G),滿足當(dāng)d(e1,e2)=1時(shí),|f(e1)-f(e2)|≥2;當(dāng)d(e1,e2)=2時(shí), 有|f(e1)-f(e2)|≥1.

圖的L(2,1)-邊標(biāo)號(hào)數(shù)λ’(G).顯然，對(duì)圖G的邊標(biāo)號(hào)研究相當(dāng)于對(duì)于對(duì)其線圖L(G)的點(diǎn)標(biāo)號(hào)研究.近年來(lái),L(2,1)-邊標(biāo)號(hào)問(wèn)題也被廣泛地研究[5-19].

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

2 圖的分解

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

為了文章敘述簡(jiǎn)潔，定義一下概念和符號(hào).我們稱(chēng)F的一條邊e是圈關(guān)聯(lián)邊,如果e與C內(nèi)的一個(gè)圈關(guān)聯(lián).如果一個(gè)圈C的兩條圈關(guān)聯(lián)邊e,f滿足dG∪e∪f(wàn)(e,f)=2,則我們稱(chēng)e是f的圈間隔邊.記I(e)表示e的圈間隔邊集.我們稱(chēng)一條邊e是單邊,如果e連接著C內(nèi)的兩個(gè)圈.為了方便起見(jiàn),記N(e)表示邊e的鄰邊集,l(e)表示邊e的標(biāo)號(hào).記l(A)表示邊集A的標(biāo)號(hào)集.

令E1={e|e是一條圈關(guān)聯(lián)邊,存在另一條圈關(guān)聯(lián)邊f(xié)與e相鄰}.

令E2是所有不屬于E1的圈關(guān)聯(lián)邊組成的集合.

令E3=F-E1-E2.

令A(yù)={0,1,2,3,4},B={8,9,…15,16}.我們稱(chēng)數(shù)a∈C是邊e的最小有效數(shù),如果a是用于標(biāo)號(hào)e的數(shù)集C中滿足正常L(2,1)-邊-標(biāo)號(hào)的最小數(shù).

2.1 標(biāo)號(hào)算法

2.1.1 標(biāo)E1的邊

算法E1

步驟1 若存在三條未標(biāo)號(hào)的兩兩相鄰邊e,f,g∈E1.分別取A中的最小有效數(shù)a,b標(biāo)給e,f,g中的兩條邊,使得能被a,b正常標(biāo)號(hào)的邊優(yōu)先標(biāo)號(hào).取{4,5,6}中的最小有效數(shù)標(biāo)給余下的邊.

步驟2 若存在兩對(duì)未標(biāo)號(hào)鄰邊e,f∈E1和g,h∈E1.滿足e,f和g,h分別與一條邊的兩端點(diǎn)相關(guān)聯(lián).分別取{0,1,2,3}中的最小有效數(shù)a,標(biāo)給e,f和g,h中的各一條邊,使得能被a,b正常標(biāo)號(hào)的邊優(yōu)先標(biāo)號(hào).取{3,4,,6}中的最小有效數(shù)標(biāo)給余下的兩條邊.

步驟3 若存在一對(duì)未標(biāo)號(hào)鄰邊e,f∈E1.分別取A中的最小有效數(shù)a,b標(biāo)給e,f,使得能被a正常標(biāo)號(hào)的邊優(yōu)先標(biāo)號(hào),滿足(a,b)≠(1,4).

定理2 算法E1能在線性時(shí)間內(nèi)用A∪{5,6}內(nèi)的數(shù)對(duì)E1進(jìn)行正常的L(2,1)-邊標(biāo)號(hào).

證明:設(shè)e,f,g是步驟1所述三條未標(biāo)號(hào)邊.不失一般性,設(shè)邊e滿足0?l(I(e))，則e能被標(biāo)為0.2?l(I(f))(同理可得g,同),則f能被標(biāo)為2,{4,5,6}中至少有1個(gè)數(shù)可以標(biāo)給g.若不然,則考慮標(biāo)號(hào)3,若3?l(I(f)),則f能被標(biāo)為3.{5,6}中至少有1個(gè)數(shù)可以標(biāo)給g.若l(I(f))={2,3}.則f能被標(biāo)為4,g能被標(biāo)為6.同理可得0∈l(I(e))的情況.

設(shè)e,f和g,h是步驟2所述兩對(duì)未標(biāo)號(hào)邊.易見(jiàn),d(e,f)=1,不失一般性,設(shè)邊e滿足0?l(I(e))(同理可得f,g,h,同),若邊g滿足1?l(I(g))(同理可得h,同),則e能被標(biāo)為0,能被標(biāo)為1.則{3,4,5,6}中至少有2個(gè)數(shù)可以標(biāo)給f,h.若不然,則考慮標(biāo)號(hào)2,若2?l(I(g)),則g能被標(biāo)為2.{3,4,5,6}中至少有2個(gè)數(shù)可以標(biāo)給f,h.若l(I(g))={1,2},則可將g標(biāo)為3.{4,5,6}中至少有2個(gè)數(shù)可以標(biāo)給f,h.同理可得0∈l(I(e))的情況.

設(shè)e,f是步驟3所述一對(duì)未標(biāo)號(hào)邊.不失一般性,設(shè)邊e滿足0?l(I(e)),則e能被標(biāo)為0.{2,3,4}中至少有1個(gè)數(shù)可以標(biāo)給f.若l(I(e)),l(I(f))不同時(shí)為{0,1}或{0,3}.則e,f能被{1,3}標(biāo)號(hào).若不然,則e,f能被{2,4}標(biāo)號(hào).

易見(jiàn),算法E1需要運(yùn)行0(E1)個(gè)時(shí)間單位.證明完畢.

2.1.2 標(biāo)E2的邊

算法E2

步驟1 若存在一條未標(biāo)號(hào)邊e是一條弦或者單邊,則取A中的最小有效數(shù)標(biāo)給e.

步驟2 若存在一條未標(biāo)號(hào)邊f(xié)∈E2,則取A∪{5,6}中的最小有效數(shù)標(biāo)給f.

定理3 算法E2能在線性時(shí)間內(nèi)用A∪{5,6}內(nèi)的數(shù)對(duì)E2進(jìn)行正常的L(2,1)-邊標(biāo)號(hào).

證明:設(shè)e是步驟1所述的一條未標(biāo)號(hào)邊.易見(jiàn)I(e)≤4,因此e至多需要避免A中的4個(gè)標(biāo)號(hào),則A中至少還有1個(gè)標(biāo)號(hào)可以標(biāo)給e.

設(shè)f是步驟2所述的一條未標(biāo)號(hào)邊.此f至多與一對(duì)非圈關(guān)聯(lián)邊g,h相鄰. 易見(jiàn),g,h未標(biāo)號(hào),且任何一條邊至多與E1內(nèi)一對(duì)已標(biāo)號(hào)鄰邊相鄰, 因此,f至多需要避免4個(gè)標(biāo)號(hào). 由于I(f)≤2,因此f至多需要避免A∪{5,6}中的6個(gè)標(biāo)號(hào),至少還有1個(gè)標(biāo)號(hào)可以給f.

易見(jiàn),算法E2需要運(yùn)行0(E2)個(gè)時(shí)間單位.證明完畢.

引理1 設(shè)e是一條圈關(guān)聯(lián)邊.若e的圈間隔邊是弦或者單邊,則執(zhí)行算法E1,E2后,e不會(huì)被標(biāo)為6.

2.1.3 標(biāo)C的邊

為了方便起見(jiàn),我們稱(chēng)單邊e是未標(biāo)號(hào)圈Ci的一條感染邊,如果e連接著Ci和一個(gè)已標(biāo)號(hào)圈Cj.

令C1= {Ci|存在Ci的一條邊,不與任何弦或感染邊相鄰}

令C2= {Ci|存在Ci的一條邊,僅與一條弦或感染邊相鄰,Ci?C1}

令C3=C-C1-C2

算法C

步驟1 若存在一個(gè)未標(biāo)號(hào)圈Ci∈C1,e1∈Ci是不與任何弦或感染邊相鄰的邊.一定的方向,記e1,e2,…,ei表示Ci的所有邊.取B中的最小有效數(shù)依次標(biāo)號(hào)e(2≤t≤i),e.

步驟2 若存在一個(gè)未標(biāo)號(hào)圈Ci∈C2,記e1∈Ci是僅與一條弦或感染邊e相鄰的邊.記e2是e的另一鄰邊.以一定的方向,記e1,e2,…,ei表示Ci的所有邊.

(1)若e2的非e相鄰圈關(guān)聯(lián)邊不是感染邊.取{7,8}中的最小有效數(shù)標(biāo)給e2,取B中的最小有效數(shù)依次標(biāo)號(hào)et(2≤t≤i),e1.

(2)若e2的非e相鄰圈關(guān)聯(lián)邊是感染邊.將e2標(biāo)為6,取B中的最小有效數(shù)依次標(biāo)號(hào)et(2≤t≤i),e1.

步驟3 若存在一個(gè)未標(biāo)號(hào)圈Ci∈C3.

(1)若存在Ci上的兩條連續(xù)感染邊或弦e,f,滿足{7,8}?l(N(e))l(N(f)),記e1是e和f都相鄰的圈邊.以一定的方向,記e1,e2,…,ei表示Ci的所有邊.取{7,8}中的最小有效數(shù)標(biāo)給e1，將e3標(biāo)為6.取B中的最小有效數(shù)依次標(biāo)號(hào)ei-t(0≤t≤i-4),e2.

(2)若對(duì)于Ci上的任何兩條連續(xù)感染邊或弦e,f,足{7,8}?l(N(e))∪l(N(f)).Ci的任何一條邊為e1,以一定的方向,記e1,e2,…,ei表示Ci的所有邊.將e1標(biāo)為6,取B中的最小有效數(shù)依次標(biāo)號(hào)et(2≤t≤i).

定理4 算法C能在線性時(shí)間內(nèi)用B∪{6,7}內(nèi)的數(shù)對(duì)C進(jìn)行正常的L(2,1)-邊標(biāo)號(hào).

證明:設(shè)Ci是C1內(nèi)的一個(gè)未標(biāo)號(hào)圈.考慮到C的邊et(2≤t≤i)至多與兩條圈關(guān)聯(lián)邊e,f相鄰.由于e,f可能是弦或感染邊.則et至多需要避免由l(et-1),l(et-2)引起的4個(gè)標(biāo)號(hào),以及由l(N(e)),l(N(f))引起的4個(gè)標(biāo)號(hào).因此,至少還有|B|-4-4=1個(gè)數(shù)可以標(biāo)給et.考慮到e1至多需要避免由l(ei),l(e2),(ei-1)和l(e3)引起的8個(gè)標(biāo)號(hào).則至少有|B|-8=1個(gè)數(shù)可以標(biāo)給e1.

設(shè)C是步驟2.1中所述C2內(nèi)的一個(gè)未標(biāo)號(hào)圈.由于e3一定與感染邊或弦相鄰,根據(jù)引理1,與e2相鄰的圈關(guān)聯(lián)邊,不會(huì)被標(biāo)為6.因?yàn)閧7,8}≠l(N(e)),所以{7,8}中至少有一個(gè)數(shù)可以標(biāo)給e2.考慮Ci的邊et(3≤t≤i-1),至少有|B|-4-4=1個(gè)數(shù)可以標(biāo)給et,2個(gè)數(shù)標(biāo)給ei.考慮到e1至多需要避免由l(ei-1),l(ei-2)和l(e3)引起5個(gè)標(biāo)號(hào),以及l(fā)(N(e))和l(e2)引起的3個(gè)標(biāo)號(hào),則至少還有1個(gè)數(shù)可以標(biāo)給e1.

設(shè)Ci是步驟2.2中所述C2內(nèi)的一個(gè)未標(biāo)號(hào)圈.易見(jiàn),單邊或弦的標(biāo)號(hào)由A給出.若與e2相鄰的圈關(guān)聯(lián)邊是弦,e2能被標(biāo)為6.假設(shè)e是感染邊,設(shè)Cj是異于Ci的與e相連的圈.易見(jiàn),在標(biāo)號(hào)Cj時(shí),Ci未被標(biāo)號(hào),則e不是Cj的感染邊,6?l(N(e)).因此,e2相鄰的圈關(guān)聯(lián)邊是感染邊或弦時(shí),e2能被標(biāo)為6.對(duì)于Ci的邊et(3≤t≤i-1),至少有|B|-4-4=1個(gè)數(shù)可以標(biāo)給et,3個(gè)數(shù)可以標(biāo)給ei,2個(gè)數(shù)可以標(biāo)給e1.

設(shè)Ci是步驟3.1中所述C3內(nèi)的一個(gè)未標(biāo)號(hào)圈.見(jiàn){7,8}中至少有一個(gè)數(shù)可以標(biāo)給e1.由于e3與兩條感染邊或弦相鄰,e3能被標(biāo)為6.此,至少還有|B|-4-4=1個(gè)數(shù)可以標(biāo)給ei-t(0≤t≤i-4).考慮e2至多需要避免l(ei),l(e4)引起2個(gè)標(biāo)號(hào),l(e1)引起的2個(gè)標(biāo)號(hào),以及感染邊引起的4個(gè)標(biāo)號(hào),至少還有1個(gè)數(shù)可以標(biāo)給e2.

設(shè)Ci是步驟3.2中所述C3內(nèi)的一個(gè)未標(biāo)號(hào)圈. 易見(jiàn),e1能被標(biāo)為6. 至少有|B|-4-3=2個(gè)數(shù)可以標(biāo)給et(2≤t≤i), 考慮ei至多需要避免l(ei-1),l(ei-2)和l(e2)引起的5個(gè)標(biāo)號(hào),及感染邊引起的3個(gè)標(biāo)號(hào),則至少還有1個(gè)數(shù)可以標(biāo)給ei.

易見(jiàn),算法C需要運(yùn)行0(C)個(gè)時(shí)間單位,即能在線性時(shí)間內(nèi)用B∪{6,7}內(nèi)的數(shù)對(duì)C進(jìn)行正常的L(2,1)-邊標(biāo)號(hào).證明完畢.

2.1.4 標(biāo)E3的邊

易見(jiàn),森林F可以由一系列的樹(shù)T1,T2,T3…Tn組成,其中Ti∩Tj=φ,1≤i,j≤n,i≠j.

為方便起見(jiàn),我們稱(chēng)E3?F內(nèi)的邊e是特殊邊,如果e與圈關(guān)聯(lián)邊相鄰.

令E32={e|e是一條特殊邊,且e?E31}

算法E3

步驟1 對(duì)任意的一棵樹(shù)T∈F,定T內(nèi)任意一個(gè)葉子點(diǎn)v作為根點(diǎn), 設(shè)邊e=xy∈T, 則記d(v,e)=min{d(v,x),d(v,y)}表示v與e的距離.

步驟2 以根點(diǎn)v∈T的距離由近到遠(yuǎn),若存在一對(duì)特殊邊e,e′,滿足d(v,e)=d(v,e),取{5,6}中的最小有效數(shù)優(yōu)先標(biāo)號(hào)e,e′中相鄰較多圈關(guān)聯(lián)邊的邊(若不能被5正常標(biāo)號(hào),則考慮鄰邊),若不能正常標(biāo)號(hào),則不進(jìn)行.

記e,e′是距離v最遠(yuǎn)的一對(duì)特殊邊,ei-1是距離ei最近的標(biāo)號(hào)特殊邊.

(1)若d(ei-1,ei)=2,l(ei-1)=6

(2)若d(i-1,ei)>2,且存在一條與v更近,與ei距離為2的圈關(guān)聯(lián)邊.

(3)若不存在一條與v更近,且與ei距離為2的圈關(guān)聯(lián)邊.

(2)若e′∈E31與兩條圈關(guān)聯(lián)邊相鄰.記與e,e′相鄰的圈關(guān)聯(lián)邊為f.若l(f)=5,記e′的非f圈關(guān)聯(lián)鄰邊為f′.取消f,f′標(biāo)號(hào).取A∪{5}中的最小有效數(shù)依次標(biāo)號(hào)f,f′.

(3)若e′∈E32, 存在e′的鄰邊ei是特殊邊, 且l(ei)=6.則取消ei標(biāo)號(hào),將e′標(biāo)為6.

(4)若e′∈E32,e′未被標(biāo)為5或6,將e標(biāo)為6.

步驟4 以根點(diǎn)v∈T的距離由近到遠(yuǎn),取B∪{6,7}中的最小有效數(shù)依次標(biāo)給T內(nèi)未標(biāo)號(hào)邊,且滿足與v距離相同的一對(duì)鄰邊,特殊邊(相鄰較多圈關(guān)聯(lián)邊)優(yōu)先被標(biāo)號(hào).

定理5 算法E3能在線性時(shí)間內(nèi)用{0,1,…,15,16}內(nèi)的數(shù)對(duì)E3進(jìn)行正常的L(2,1)-邊標(biāo)號(hào).

設(shè)T是步驟5中所述一棵未完全標(biāo)號(hào)樹(shù).對(duì)T進(jìn)行歸納假設(shè). 當(dāng)T=1時(shí), 可以由B∪{6,7}內(nèi)的數(shù)標(biāo)號(hào).假設(shè)T=k-1時(shí),B∪{6,7}能對(duì)T內(nèi)未標(biāo)號(hào)邊進(jìn)行正常L(2,1)-邊標(biāo)號(hào).證明當(dāng)T=k時(shí),結(jié)論也成立.設(shè)e∈T是離v最遠(yuǎn)的一條未標(biāo)號(hào)邊.根據(jù)歸納假設(shè),T-e的未標(biāo)號(hào)邊能被B∪{6,7}正常的L(2,1)-邊標(biāo)號(hào).考慮e的可能情況:

情況1 若e不是特殊邊.則e至多需要避免由l(N(e))引起的6個(gè)標(biāo)號(hào),離根點(diǎn)v較近的,與e距離為2的兩條邊的2個(gè)標(biāo)號(hào).因此至少有|B|+2-6-2=3個(gè)數(shù)可以標(biāo)給e.

情況2 若e是特殊邊,且e∈E31.

(1)若e與4條圈關(guān)聯(lián)邊相鄰.易見(jiàn),e至多需要避免距離為2的8條圈邊的8個(gè)標(biāo)號(hào),圈關(guān)聯(lián)邊的可能標(biāo)號(hào)6,則至少有|B|-8=1個(gè)數(shù)可以標(biāo)給e.

(2-1)若e′如步驟3.1所述,當(dāng)e′被{0,2,4}中的數(shù)標(biāo)號(hào),則B中至少有|B|-6=3個(gè)數(shù)可以標(biāo)給e. 當(dāng)e′未被{0,2,4}標(biāo)號(hào), 則e至多需要避免l(e′)引起的3個(gè)標(biāo)號(hào),距離為2的6條圈邊的6個(gè)標(biāo)號(hào), 圈關(guān)聯(lián)邊的可能標(biāo)號(hào)5,B∪{7}至少有|B|+1-6-3=1個(gè)數(shù)可以標(biāo)給e.

(2-2)若e′如步驟3.2所述,則e至多需要避免l(e′)引起的3個(gè)標(biāo)號(hào),距離為2的7條邊的7個(gè)標(biāo)號(hào),B∪{6,7}至少有|B|+2-3-7=1個(gè)數(shù)可以標(biāo)給e.

(2-3)若e′是已標(biāo)號(hào)的特殊邊,則l(e′)≤6.則B至少有|B|-2-6=1個(gè)數(shù)可以標(biāo)給e.

(3)若e與兩條圈關(guān)聯(lián)邊相鄰.易見(jiàn),e至多需要避免離根點(diǎn)v更近的鄰邊引起的3個(gè)標(biāo)號(hào),距離為2的6條邊的6個(gè)標(biāo)號(hào),圈關(guān)聯(lián)邊的可能標(biāo)號(hào)5,B∪{7}至少有|B|+1-6-3=1個(gè)數(shù)可以標(biāo)給e.

情況3 若e是特殊邊,且e∈E32.記e的一條鄰邊為e′,滿足d(v,e)=d(v,e′).(若不存在e′,易見(jiàn)B∪{7}中至少有1個(gè)數(shù)可以標(biāo)給e.)

(1)若e與兩條圈關(guān)聯(lián)邊相鄰.

(1-1)若l(e′)≤5,則e至多需要避免離根點(diǎn)v更近的鄰邊引起的3個(gè)標(biāo)號(hào),距離為2的6條邊的6個(gè)標(biāo)號(hào),B∪{7}中至少有|B|+1-6-3=1個(gè)數(shù)可以標(biāo)給e.

(1-2)若l(e′)=6.若存在一條標(biāo)號(hào)特殊邊f(xié),滿足l(f)=5,d(e,f)=2,則B中至少有|B|-3-4=2個(gè)數(shù)可以標(biāo)給e.若不存在,則根據(jù)步驟2.2.2,B中至少有|B|-4-4=1個(gè)數(shù)可以標(biāo)給e.

(2)若e與一條圈關(guān)聯(lián)邊相鄰.

(2-1)若l(e′)≤6,B中至少有|B|-5-2=2個(gè)數(shù)可以標(biāo)給e.

(2-2)若l(e′)>6,根據(jù)步驟2.1.1,e至多需要避免鄰邊引起的6個(gè)標(biāo)號(hào),距離為2的2條邊的2個(gè)標(biāo)號(hào),B中至少有|B|-6-2=1個(gè)數(shù)可以標(biāo)給e.

由此可得,T的邊能被B∪{6,7}正常標(biāo)號(hào),歸納假設(shè)成立.

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

如上所述,我們能在線性時(shí)間內(nèi)用{0,1,…,15,16}對(duì)G的邊進(jìn)行標(biāo)號(hào).且對(duì)于滿足Δ(G)=3的簡(jiǎn)單圖G,有λ’(G)≤16,Griggs和Yeh猜想成立.