毛毛蟲樹的L(3,2,1)-標號問題

張小玲

(集美大學師范學院，福建 廈門 361021)

圖的距離標號問題源于無線電網絡中的頻率分配問題，即給每個無線電發射臺分配一個頻率，使得相互干擾的無線電發射臺所分配的頻率間隔落在允許的范圍之內.關于頻率分配問題的研究已有數十年的歷史，1980年,Hale[1]將此問題歸結成圖的T-著色問題.1992年，Griggs等[2]將該問題抽象為圖的距離標號問題，并考慮了更一般的L(p，q)-標號問題.從此，圖的L(p，q)-標號問題得到了廣泛研究，詳見文獻[3-4].

2004年，學者們開始研究圖的L(3,2,1)-標號問題.Griggs等[2]已經證明了確定一般圖G的L(3,2，1)標號數是NP-困難的問題.因而，確定一些特殊圖類的L(3,2，1)標號數或給出L(3,2,1)標號數的上下界成為極具意義的研究課題.如，Shao[5]研究了Kneser圖,Halin圖等的L(3,2,1)-標號，并給出這些圖類的L(3,2,1)標號數的上下界.Chia等[6]考慮了一般圖和樹的L(3,2,1)標號數的上下界.Clipperton[7]確定了路、圈、n-元樹、完全圖和完全二部圖的L(3,2，1)標號數.同時也證明了對任意毛毛蟲樹T,有2Δ+1≤λ3,2,1(T)≤2Δ+2.我們在已有研究的基礎上，對毛毛蟲樹的L(3,2,1)-標號進行研究，糾正了Clipperton等[7]的一個錯誤，并完全確定了最大度不小于4的毛毛蟲樹的L(3,2,1)標號數.

1 預備知識

對于任意非負整數i,j(i

定義1圖G的L(3,2,1)-標號是指從頂點集V(G)到非負整數集Z*的一個映射f,滿足：對于任意兩個不同頂點u和v,若d(u,v)=i(i=1,2,3),則|f(u)-f(v)|≥4-i.若圖G的一個L(3,2,1)-標號中的所有像元素都不超過整數k,則稱之為圖G的k-L(3,2,1)-標號.圖G的L(3,2,1)標號數，記作λ3,2,1(G),是使得圖G存在k-L(3,2,1)-標號的最小整數k.

引理1[6]若f是G的一個k-L(3,2,1)-標號，則映射f′:V(G)→[0,k]也是G的k-L(3,2,1)-標號，其中f′(v)=k-f(v).

引理2[6]設T是一棵樹，則2Δ+1≤λ3,2,1(T)≤2Δ+3.進一步地，若λ3,2,1(T)=2Δ+1且f是T的一個(2Δ+1)-L(3,2,1)-標號，則對于T的每個Δ-點v,均有f(v)∈ {0,2Δ+1}.

注1根據引理2,若λ3,2,1(T)=2Δ+1且f是T的一個(2Δ+1)-L(3,2,1)-標號，則對于每個Δ-點v,都有f(v)∈{0,2Δ+1}.并且當f(v)=0時，有f(N(v))=O[3,2Δ+1];當f(v)=2Δ+1時，有f(N(v))=E[0,2Δ-2].

根據引理2和注1，不難得到如下定理.

定理1設T是一棵樹.若T滿足條件(i)或(ii),則λ3,2,1(T)≥2Δ+2.

(i)T中存在兩個Δ-點v1,v2,使得d(v1,v2)=2;

(ii)T中存在三個Δ-點v1,v2,v3,使得對于1≤i,j≤3,都有d(vi,vj)≤3.

毛毛蟲樹是指去掉懸掛點和與其關聯的懸掛邊后只剩下一條路(記為P=v1v2…vn)的樹，其中P稱為毛毛蟲樹的脊椎，vi稱為毛毛蟲樹的脊椎點.設T是毛毛蟲樹，若Δ≤2，則T是一條路.下文將證明對于最大度不小于4的毛毛蟲樹T，條件(i)是λ3,2,1(T)=2Δ+2的充要條件.

Clipperton等[7]研究了毛毛蟲樹的L(3,2,1)-標號，并給出如下結果.

定理2[7]設Pn是一條具有n個頂點的路，則

定理3[7]設T是毛毛蟲樹且Δ≥3,則2Δ+1≤λ3,2,1(T)≤2Δ+2.若T中任意4個連續的脊椎點至多包含兩個Δ-點，則λ3,2,1(T)=2Δ+1.

注2定理3的后半部分是錯誤的.事實上，如果T只包含兩個距離為2的Δ-點，顯然滿足T中任意4個連續的脊椎點至多包含兩個Δ-點，但由定理1可得λ3,2,1(T)≥2Δ+2.

2 主要結果

定理4設T是毛毛蟲樹且Δ≥4.那么λ3,2,1(T)=2Δ+1當且僅當T中不存在兩個距離為2的Δ-點.

證明必要性.反證，若T包含兩個距離為2的Δ-點，則根據定理1，有λ3,2,1(T)≥2Δ+2.結合定理3,可知λ3,2,1(T)=2Δ+2,但這與假設相矛盾.

充分性.設v1v2…vn是T的脊椎，vi1,vi2,…,vik是T的所有Δ-點，其中i1

首先，用0,2Δ-1,2,2Δ+1的模式循環標記vi1vi1-1…v1.一般地，假設vij-1…vij已經標記，其中2≤j≤k.下面分5種情形標記vij…vij+1.

情形1d(vij,vij+1)=1.

若(f(vij-1),f(vij))=(5,0)或(2Δ-1,0)，則vijvij+1標記X1=0(2Δ+1).

情形2d(vij,vij+1)=4t+3,其中t≥0.

若(f(vij-1),f(vij))=(5,0)，則vij…vij+1標記X2.

若(f(vij-1),f(vij))=(2Δ-1,0)或(2Δ+1,0)，則vij…vij+1標記X′2.

其中

情形3d(vij,vij+1)=4t+4,其中t≥0.

若(f(vij-1),f(vij))=(5,0)或(2Δ-1,0)或(2Δ+1,0)，則vij…vij+1標記X3.

其中

情形4d(vij,vij+1)=4t+5,其中t≥0.

若(f(vij-1),f(vij))=(5,0)或(2Δ-1,0)或(2Δ+1,0)，則vij…vij+1標記X4.

其中

情形5d(vij,vij+1)=4t+6,其中t≥0.

若(f(vij-1),f(vij))=(5,0)或(2Δ-1,0)或(2Δ+1,0)，則vij…vij+1標記X5.

其中

接下來，若f(vik)=0,則用0,3,6,9的循環模式標記vikvik+1…vn;對稱地，若f(vik)=2Δ+1,則用2Δ+1,2Δ-2,3,0的循環模式標記vikvik+1…vn.

最后，若f(vi)為奇數，則用E[0,2Δ]{f(vi)±1,f(vi-1),f(vi+1)}標記vi的葉子鄰點;若f(vi)為偶數，則用O[1，2Δ+1]{f(vi)±1,f(vi-1),f(vi+1)}標記vi的葉子鄰點.

不難證明，上述每種情形下的片段均是可行的(2Δ+1)-L(3,2,1)-標號且每種情形下的標號都可相互銜接.因而，f是T的一個(2Δ+1)-L(3,2,1)-標號.故λ3,2,1(T)=2Δ+1.

3 結 論

Clipperton[7]證明了對任意的最大度不小于3的毛毛蟲樹T,都有2Δ+1≤λ3,2,1(T)≤2Δ+2.且當T中任意4個連續的脊椎點至多包含兩個Δ-點時，有λ3,2,1(T)=2Δ+1.我們發現這個結果的后半部分是錯誤的.本文糾正了這一錯誤，并完全確定了最大度不小于4的毛毛蟲樹的L(3,2,1)標號數.