考慮含有完全圖K4的圖的補(bǔ)圖的L（2，1）-標(biāo)號的島序列＊

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

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

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

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

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

定義1 圖G的一個(gè)路覆蓋是G中包含G的所有頂點(diǎn)的點(diǎn)不交的路的集合．

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

定義2 圖G的一個(gè)輕點(diǎn)為度不大于2的點(diǎn)，重點(diǎn)為G中度大于2的點(diǎn)．

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

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

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

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

2 圖G路覆蓋與補(bǔ)圖GC的島序列

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

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

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

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

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

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

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

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

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

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

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

證明 由于p≥2，通過對p進(jìn)行歸納來證明．

當(dāng)p＝2時(shí)，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

① 兩個(gè)葉子點(diǎn)懸掛在不同的重點(diǎn)．圖1給出了圖G 的兩個(gè)最小路覆蓋（P1，P2）和（P3，P4），其中P1為以兩個(gè)葉子點(diǎn)為端點(diǎn)的最長路，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）

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

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

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

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

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

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

若l1′≥l2′且l1′≤l3′，則l4′≤l2′≤l1′≤l3′，λ（GC）-標(biāo)號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）-標(biāo)號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容許兩個(gè)不同的島序列．

所以p＝2時(shí)，GC容許兩個(gè)不同的島序列．

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

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

因此GC容許兩個(gè)不同的島序列．

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

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

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

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

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

3 結(jié)論

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

［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．