葉 林 李 涌

(臺州第一技師學院,浙江 臺州 317500)

1 基礎知識

圖G的一個L(2,1)-標號問題來自于無線電的頻率分配問題[1-2].本文中G的點集和邊集分別用V(G)和E(G)表示.對任意的v∈V(G),用d(v)表示G中點v的度數(shù)；對任意的x,y∈V(G),d(x,y)表示點x,y之間的距離.對任意的e1,e2∈E(G),d(e1,e2)表示邊e1,e2之間的距離.

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

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

圖的L(2,1)-邊標號數(shù)λ’(G).顯然，對圖G的邊標號研究相當于對于對其線圖L(G)的點標號研究.近年來,L(2,1)-邊標號問題也被廣泛地研究[5-19].

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

2 圖的分解

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

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

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

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

令E3=F-E1-E2.

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

2.1 標號算法

2.1.1 標E1的邊

算法E1

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

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

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

定理2 算法E1能在線性時間內用A∪{5,6}內的數(shù)對E1進行正常的L(2,1)-邊標號.

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

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

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

易見,算法E1需要運行0(E1)個時間單位.證明完畢.

2.1.2 標E2的邊

算法E2

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

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

定理3 算法E2能在線性時間內用A∪{5,6}內的數(shù)對E2進行正常的L(2,1)-邊標號.

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

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

易見,算法E2需要運行0(E2)個時間單位.證明完畢.

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

2.1.3 標C的邊

為了方便起見,我們稱單邊e是未標號圈Ci的一條感染邊,如果e連接著Ci和一個已標號圈Cj.

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

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

令C3=C-C1-C2

算法C

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

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

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

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

步驟3 若存在一個未標號圈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ù)標給e1，將e3標為6.取B中的最小有效數(shù)依次標號ei-t(0≤t≤i-4),e2.

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

定理4 算法C能在線性時間內用B∪{6,7}內的數(shù)對C進行正常的L(2,1)-邊標號.

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

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

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

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

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

易見,算法C需要運行0(C)個時間單位,即能在線性時間內用B∪{6,7}內的數(shù)對C進行正常的L(2,1)-邊標號.證明完畢.

2.1.4 標E3的邊

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

為方便起見,我們稱E3?F內的邊e是特殊邊,如果e與圈關聯(lián)邊相鄰.

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

算法E3

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

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

記e,e′是距離v最遠的一對特殊邊,ei-1是距離ei最近的標號特殊邊.

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

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

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

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

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

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

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

定理5 算法E3能在線性時間內用{0,1,…,15,16}內的數(shù)對E3進行正常的L(2,1)-邊標號.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由此可得,T的邊能被B∪{6,7}正常標號,歸納假設成立.

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

如上所述,我們能在線性時間內用{0,1,…,15,16}對G的邊進行標號.且對于滿足Δ(G)=3的簡單圖G,有λ’(G)≤16,Griggs和Yeh猜想成立.