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

張小玲

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

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

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

1 預備知識

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

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

根據(jù)引理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.

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

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

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

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

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

2 主要結(jié)果

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

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

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

首先，用0,2Δ-1,2,2Δ+1的模式循環(huán)標記vi1vi1-1…v1.一般地，假設vij-1…vij已經(jīng)標記，其中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的循環(huán)模式標記vikvik+1…vn;對稱地，若f(vik)=2Δ+1,則用2Δ+1,2Δ-2,3,0的循環(huán)模式標記vikvik+1…vn.

最后，若f(vi)為奇數(shù)，則用E[0,2Δ]{f(vi)±1,f(vi-1),f(vi+1)}標記vi的葉子鄰點;若f(vi)為偶數(shù)，則用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 結(jié) 論

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