雒金梅，余 航，任樹鑫，郭海防

（西安工業(yè)大學(xué) 北方信息工程學(xué)院，西安710200）

L（2，1）-標號，由Griggs和Roberts提出的，是產(chǎn)生于各種頻率分配問題的一個頂點標號問題，目的是找到最小的頻率使用范圍，同時確保充分靠近的兩個傳輸機分配到的傳輸頻率的差不小于一個給定的正數(shù)［1-2］．L（p，q）-標號是圖G 的頂點集到整數(shù)集的一個映射，并且滿足任意兩個相鄰的頂點的標號差至少為p，任意兩個距離為2的頂點標號差至少為q，若p＝2，q＝1那么L（p，q）-標號就是著名的L（2，1）-標號，它是L（p，q）-標號的一種特殊情況．關(guān)于L（p，q）-標號，一些專家已經(jīng)對某些特殊的簡單圖做了研究，特別是對L（2，1）-標號進行了討論．對任意的圖，文獻［3］研究了圖變量λ（G）和圖G的其他圖變量，如圖G的色數(shù)χ（G），最大度Δ＝Δ（G）之間的關(guān)系，已經(jīng)得到各種類型的圖的λ數(shù)，如樹，圈，路，3-連通圖．文獻［4］研究了弦圖的λ數(shù)．另外文獻［5］研究了λ（G）、圖變量c（GC）（圖G的補圖的路覆蓋數(shù)）及圖G的頂點數(shù)之間的關(guān)系．L（2，1）-標號的推廣已經(jīng)在研究．文獻［6-9］證明了當(dāng)c（GC）≥2，λ（G）＝n＋c（GC）-2，其中n為圖G的頂點數(shù)，給出了路覆蓋的一個更一般的結(jié)果的完全證明，證明了圖G的補圖的一個路覆蓋導(dǎo)出了G的一個有c（GC）-1個洞的λ（G）標號．文獻［10］提出了ρ（G）≥1，導(dǎo)出兩個不同島序列的λ（G）標號的連通圖的存在性，證明了2-稀疏數(shù)的補圖是容許至少兩個不同島序列的連通圖．文中給出了另一類圖的λ數(shù)和洞指數(shù)ρ（G）的關(guān)系，路覆蓋數(shù)和L（2，1）-標號的島序列，研究某類含有完全圖K4的圖的路覆蓋數(shù)，以期在兩種最小路覆蓋之下均證明其補圖的兩個不同的λ標號導(dǎo)出的兩個島序列不同．

1 L（2，1）-標號的相關(guān)知識

L（2，1）-標號問題是類似于頻率分配問題的頂點標號問題．圖G的一個L（2，1）-標號是從G的頂點集V（G）到非負整數(shù)集｛0，1，…，k｝的一個函數(shù)f，并且滿足：若d（x，y）＝1，則｜f（x）-f（y）｜≥2，若d（x，y）＝2，則｜f（x）-f（y）｜≥1．其中d（x，y）表示頂點x和頂點y之間的距離．這些標號問題已經(jīng)被用來模仿無線電分配問題［3］．圖G的使用集合｛0，1，…，k｝（未必是所有的元素）中的元素進行標號的一個L（2，1）-標號叫做一個k標號．使得G有一個k標號的最小的k叫做G的λ數(shù)，用λ（G）來表示．一個λ（G）標號簡記為λ標號．稱一個k標號有洞h（0＜h＜k），若h在這個標號中沒有被使用．G的所有λ（G）標號的洞的個數(shù)的最小值叫做G的洞指數(shù)，用ρ（G）來表示．不難看出，若一個λ（G）標號恰有ρ（G）個洞，那么任意兩個洞是不連續(xù)的［2］．一個有ρ（G）個洞的圖G的一個給定λ標號的島是指用于標號的連續(xù)整數(shù)的極大集合．一個有ρ（G）個洞的圖G的一個給定λ標號的島序列是指島基數(shù)按不減順序的有序排列（這個定義允許基數(shù)重復(fù)）．

定義1 圖G的一個路覆蓋是G中包含G的所有頂點的點不交的路的集合．

圖G的路覆蓋數(shù)用c（G）來表示，是G的具有最少路數(shù)的一個路覆蓋中路的數(shù)目．恰有c（G）條路的一個路覆蓋叫做G的最小路覆蓋．

定義2 圖G的一個輕點為度不大于2的點，重點為G中度大于2的點．

圖G的一個藤S定義為G中的一條極大路且滿足一個端點是葉子點，其余點在G中為輕點．

為了書寫方便，用GC表示圖G的補圖．

引理1［1］G是一個有n個頂點的圖，那么c（GC）≥2當(dāng)且僅當(dāng)λ（G）＝n＋c（GC）-2．

引理2［1］G是一個有n個頂點的圖，且λ（G）≥n-1，那么ρ（G）＝c（GC）-1．

2 圖G路覆蓋與補圖GC的島序列

引理3 設(shè)G為含有完全圖K4且圖中除K4中外沒有相鄰的重點，e為圖中與兩個輕點關(guān)聯(lián)的一條邊，若e?K4，那么e包含在G的每個最小路覆蓋中．

證明 設(shè)u和w為與e關(guān)聯(lián)的兩個輕點．假設(shè)存在G的不包含e的一個最小路覆蓋，因為u和w為輕點，那么在這個最小路覆蓋中存在著以u為端點的路P和以w為端點的路Q，并且邊e既不在P中，也不在Q中，由于e?K4，P和Q是不同的，因此P＋Q＋e是一條路．用P＋Q＋e取代原來的路P和Q，得到了有路數(shù)更少的G的一個路覆蓋，與假設(shè)這個路覆蓋為最小路覆蓋矛盾，因此e包含在G的每個最小路覆蓋中．

引理4 G是有m（m ≥1）條邊，n個頂點，p（≥2）個葉子點的某類含有完全圖K4的圖（且G中除K4外不含相鄰的重點）．那么c（G）＝p．

證明 由于p≥2，對p用歸納法．

p＝2時，由于G中含有完全圖K4，c（G）＝2＝p．

p＞2時，假設(shè)圖G中含有k（2≤k＜p）個葉子點時結(jié)論成立．

設(shè)S為G中的與重點v關(guān)聯(lián)的藤，則G-S為有p-1個葉子點的圖，由歸納假設(shè)，c（G-S）＝p-1，若把S增加到G-S的任一個有p-1條路的最小路覆蓋中，得到了圖G的含有p條路的路覆蓋．所以c（G）≤p．

假設(shè)c（G）≤p-1．考慮圖G的任一個最小路覆蓋．

由于S是這個最小路覆蓋中某條路P′的子圖，若v?P′，則P′＝S．把S從這個最小路覆蓋中刪除，得到了G-S的有c（G）-1≤p-2條路的路覆蓋，與c（G-S）＝p-1矛盾．所以v∈P′，且v為P′的中間點，設(shè)e為P′中與v和S關(guān)聯(lián)的邊，f為與v關(guān)聯(lián)的另一條邊且f?P′，則與f關(guān)聯(lián)的另一個點u必為輕點，那么u一定是G中的最小路覆蓋中某條不同于P′的路Q的端點，用S來代替P′，用Q＋P′-S-e來代替Q，得到了有c（G）條路的另一個最小路覆蓋，把S從G中刪除，得到了G-S的有c（G）-1≤p-2條路的最小路覆蓋．與c（G-S）＝p-1矛盾．

綜上所述c（G）＝p，得證．

定理1 G是一個有m（m≥1）條邊，n個頂點，p（≥2）個葉子點，含有完全圖K4且圖中除K4中外沒有相鄰的重點那么GC容許至少兩個不同的島序列．

證明 由于p≥2，通過對p進行歸納來證明．

當(dāng)p＝2時，c（G）＝p＝2，c（G）≥2

由引理1有λ（GC）＝n＋c（G）-2＝n＋2-2＝n．

由引理2有ρ（GC）＝c（G）-1＝2-1＝1

① 兩個葉子點懸掛在不同的重點．圖1給出了圖G 的兩個最小路覆蓋（P1，P2）和（P3，P4），其中P1為以兩個葉子點為端點的最長路，P1＝u1u2，…，ul1，P2＝v1v2，…，vl2；P3＝x1x2，…，xl3，P4＝y(tǒng)1y2，…，yl4．

圖1 最小路覆蓋（P1，P2）和（P3，P4）Fig．1 Minmum path covering（P1，P2）and（P3，P4）

這兩個最小路覆蓋導(dǎo)出了GC的恰有ρ（GC）＝1個洞的兩個λ（GC）-標號f1和f2，其中

由于l1＝n-1，l2＝1，1＜l3＜l1因此由f1導(dǎo)出的的島序列不同于由f2導(dǎo)出的島序列，故GC容許兩個不同的島序列．

②兩個葉子點懸掛在同一個重點．圖2給出了圖G 的兩個最小路覆蓋（P1′，P2′）和（P3′，P4′）

圖2 最小路覆蓋（P1′，P2′）和（P3′，P4′）Fig．2 Minmum path covering（P1′，P2′）and（P3′，P4′）

這兩個最小路覆蓋導(dǎo)出了GC的恰有ρ（GC）＝1個洞的兩個λ（GC）-標號f1′和f2′，

若l1′ ＜l2′，則l4′ ＜l1′ ＜l2′ ＜l3′．則λ（GC）-標號f1′ 導(dǎo)出的GC的島序列為（l1′，l2′），由標號f2′ 導(dǎo) 出 的GC的 島 序 列 為 （l4′，l3′），顯 然 （l1′，l2′）不 同 于（l4′，l3′）．

若l1′≥l2′且l1′≤l3′，則l4′≤l2′≤l1′≤l3′，λ（GC）-標號f1′導(dǎo)出的GC的島序列（l2′，l1′）不同于f2′ 導(dǎo)出的GC的島 序列（l4′，l3′）．

若l1′ ≥l2′ 且l1′ ＞l3′，則 由 于l3′ ＞l2′，故 有l(wèi)1′ ＞l3′ ＞l2′．又 由 于l1′ ＋l2′ ＝l3′ ＋l4′，所 以λ（GC）-標號f1′ 導(dǎo)出的GC的島序列為（l2′，l1′），f2′ 導(dǎo) 出 的GC的 島 序 列 為 （l4′，l3′）或 （l3′，l4′），顯然 （l2′，l1′）不 同 于 （l4′，l3′）或（l3′，l4′）．

由f1′導(dǎo)出的島序列不同于由f2′導(dǎo)出的島序列，從而GC容許兩個不同的島序列．

所以p＝2時，GC容許兩個不同的島序列．

假設(shè)p＞2，對每個有k（2≤k＜p）個葉子點含有完全圖K4且圖中除K4中外沒有相鄰的重點的圖G，GC容許至少兩個不同的島序列．

考慮任意一個有p（＞2）個葉子點的圖G，選擇G的一個藤S，則G-S為有p-1≥2個葉子點的滿足假設(shè)條件的圖，根據(jù)歸納假設(shè)，H ＝（G-S）容許兩個不同的島序列．設(shè)g1和g2為H的有ρ（H）個洞、導(dǎo)出兩個不同島序列的λ（H）標號，把這兩個標號延拓到S＝v1v2…vs，通過給vi（i＝1，2，…，s）分配標號λ（H）＋i＋1，這兩個新的標號即為GC的有ρ（H）＋1個洞的（λ（H）＋s＋1）-標號．

因此GC容許兩個不同的島序列．

定理2 G是一有p（p≥2）個葉子點的含有完全圖K4且圖中除K4中外沒有相鄰的重點，則GC是連通的．

當(dāng)u和z在GC中相鄰時，顯然成立．

假設(shè)u和z在GC中不相鄰．由于v1，v2為G中的葉子點，所以u和z中至少有一個頂點在GC中與vi（i＝1，2）相鄰．若u和z在GC中都與某個vi相鄰，則uviz即為GC中連通u和z的路．若u和v1在GC中相鄰，z和v2在GC中相鄰，由于v1，v2為G中的葉子點，且圖G不為路，所以v1，v2在G中必不相鄰，則在GC中必相鄰，從而uv1v2z即為GC中連通u和z的路．

若u和z中恰有一點個在GC中與vi（i＝1，2）相鄰，而另一個點在G中與vi（i＝1，2）相鄰．不失一般性，假設(shè)u在GC中與vi（i＝1，2）相鄰，z在G中與vi（i＝1，2）相鄰，v1，v2為G中的葉子點，所以vi（i＝1，2）在GC中與除z以外的所有點相鄰．由于G為雙圈2-稀疏連通圖且G中至少有一個圈中的頂點個數(shù)多于3，故存在一個頂點w且w?｛u，z，v1，v2｝，使得w在GC中與z相鄰，顯然vi（i＝1，2）與w在GC中相鄰，所以uv1wz即為G中連通u和z的路．

綜上，GC是連通的，證畢．

3 結(jié)論

文中研究了含有完全圖K4且圖中除K4中外沒有相鄰的重點的一類圖的兩種最小路覆蓋，通過考慮這類圖的路覆蓋數(shù)和它的補圖的L（2，1）-標號下λ數(shù)和洞指數(shù)ρ（G）之間的關(guān)系，得到了它的補圖的兩個不同的L（2，1）-標號容許兩個不同的島序列，最后證明了它的補圖的連通性．

［1］ ADAMS S S，TRAZKOVICH A，TROXELL D S，et al．On the Island Sequences of Labelings with a Condition at Distance Two［J］．Disc Appl Math，2010（158）：1．

［2］ GRIGGS J R，YEH R K．Labeling Graph with a Condition at Distance Two［J］．Siam J Disc Math，2005（19）：585．

［3］ GEORGES J P，MAURO D W．On the Structure of Graphs with Non-Surjective L（2，1）-Labelings［J］．Siam J Disc Math，2005（19）：208．

［4］ SAKAI T．No-hole K-tupe（r＋1）-Distant Colorings，Discrete［J］．Appl Math，1996（64）：67．

［5］ GEORGES J P，MAURO D W，WHITTLESEY M A．Relating Path Coverings to Vertex Labelings with a Condition at Distance Two ［J］．Disc Math，1994（135）：103．

［6］ HALE W K．Frequency Assignment［J］．Theory and Applications Proc，1980（68）：1497．

［7］ CALAMONERI T．The L（h，k）-labeling Problem：A Survey and Annotated Bibliography［J］．Computer Journal，2006，49（5）：585．

［8］ GEORGES J P，MAURO D W．A Note on Collections of Graphs with Non-Surjective Lambda Labelings［J］．Discrete Appl Math，2005，46（1）：92．

［9］ CHANG G J，KUO D．The L（2，1）-Labelling Problem on Graphs，SIAM ［J］．Discrete Math，1996（9）：309．

［10］ GEORGES J P，MAURO D W，STEIN M I．Labelling Products of Complete Graphs with a Condition at Distance Two［J］．Siam J Disc Math ，2000（14）：28．