某種雙圈圖的L（2，1）－標(biāo)號(hào)的島序列

雒金梅，左連翠

（天津師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，天津 300387）

某種雙圈圖的L（2，1）－標(biāo)號(hào)的島序列

雒金梅，左連翠

（天津師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，天津 300387）

通過(guò)構(gòu)造洞指數(shù)ρ（G）≥1的一類(lèi)雙圈連通圖得到了容許至少兩個(gè)不同島序列的連通圖.

島序列；輕點(diǎn)；重點(diǎn)；2－稀疏圖；洞指數(shù)；路覆蓋數(shù)

1 引言及預(yù)備知識(shí)

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

Georges J.P.等提出洞指數(shù)ρ（G）≥1、有兩個(gè)不同島序列的連通圖是否存在的問(wèn)題［2］.Adams S.S.證明了2－稀疏樹(shù)的補(bǔ)圖容許至少兩個(gè)不同的島序列［3］.本研究給出了另一類(lèi)容許兩個(gè)不同島序列的連通圖.

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

圖G的路覆蓋數(shù)用c（G）來(lái)表示，是G的具有最少路數(shù)的一個(gè)路覆蓋中路的數(shù)目.恰有c（G）條路的一個(gè)路覆蓋稱(chēng)為G的最小路覆蓋.

定義2 一個(gè)圖稱(chēng)為2－稀疏圖如果它不包含相鄰的且度大于2的頂點(diǎn)對(duì).

圖中的一個(gè)頂點(diǎn)稱(chēng)為重點(diǎn)，如果它的度大于2，否則稱(chēng)為輕點(diǎn)，其中一度點(diǎn)稱(chēng)為葉子點(diǎn).因此一個(gè)圖是2－稀疏圖如果它不包含任何相鄰的重點(diǎn)對(duì).

下面的引理給出了路覆蓋和輕點(diǎn)或重點(diǎn)之間的聯(lián)系.為方便，用GC表示圖G的補(bǔ)圖.

引理1［3］如果v是2－稀疏圖G的一個(gè)重點(diǎn)，那么v是G的每個(gè)最小路覆蓋中的一個(gè)內(nèi)點(diǎn).

引理2［3］設(shè)G是有m（m≥1）條邊，n個(gè)頂點(diǎn)，p個(gè)葉子點(diǎn)的一個(gè)連通2－稀疏圖.如果G不是圈，那么c（G）＝p＋m－n.

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

引理4［3］設(shè)G是一個(gè)有n個(gè)頂點(diǎn)的圖，且λ（G）≥n－1，那么ρ（G）＝c（GC）－1.

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

2 主要結(jié)果

在給出主要結(jié)果之前，需要下面的引理.

引理5 設(shè)e為一個(gè)雙圈2－稀疏圖G中與兩個(gè)輕點(diǎn)關(guān)聯(lián)的一條邊，如果e不在任意一個(gè)圈中，那么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(píng)為端點(diǎn)的路P和以w為端點(diǎn)的路Q(chēng)，并且邊e既不在P中，也不在Q中.由于e不在任意一個(gè)圈中，P和Q是不同的，因此P＋Q＋e是一條路.用P＋Q＋e取代原來(lái)的路P和Q，得到了路數(shù)更少的G的一個(gè)路覆蓋，與假設(shè)矛盾，因此e包含在G的每個(gè)最小路覆蓋中.

引理6 設(shè)G是一個(gè)有m（m≥1）條邊，n個(gè)頂點(diǎn)，p個(gè)葉子點(diǎn)的連通2－稀疏圖.如果G不是圈且p＋m－n≥2，那么

證明 由引理2知c（G）＝p＋m－n≥2，由引理3知

由于p＋m－n≥2，因此有p＋m－2≥n，因此由引理4知ρ（GC）＝c（G）－1＝p＋m－n－1.

引理6確定了某類(lèi)非圈連通2－稀疏圖的λ數(shù)和洞指數(shù)之間的關(guān)系.

定理1 設(shè)G是一個(gè)有m（m≥1）條邊，n個(gè)頂點(diǎn)，p（p≥2）個(gè)葉子點(diǎn)的雙圈連通2－稀疏圖，G中每個(gè)圈中的頂點(diǎn)個(gè)數(shù)比每個(gè)藤中的頂點(diǎn)個(gè)數(shù)至少多2，且G中無(wú)偶圈，那么GC容許至少兩個(gè)不同的島序列.

證明p≥2，通過(guò)對(duì)p進(jìn)行歸納來(lái)證明.

首先證明p＝2時(shí)成立.當(dāng)p＝2時(shí)，由引理2可知c（G）＝p＋m－n＝2＋m－n，因?yàn)镚是雙圈圖，故m＝n＋1，所以c（G）＝3.由引理3可知λ（GC）＝n＋c（G）－2＝n＋3－2＝n＋1.由引理4知ρ（GC）＝c（G）－1＝3－1＝2.

考慮G中兩個(gè)圈的位置關(guān)系，分兩種情況討論.

情況1 兩個(gè)圈是點(diǎn)不交的.

情況1.1 兩個(gè)葉子點(diǎn)分別在兩個(gè)圈上.

圖1給出了G的兩個(gè)最小路覆蓋（P1，P2，P3）和（P′1，P′2，P′3），其中P1為以?xún)蓚€(gè)葉子點(diǎn)為端點(diǎn)的最長(zhǎng)路.P1＝u1u2…ul1，P2＝v1v2…vl2，P3＝w1w2…wl3；P′1＝x1x2…xl′1，P′2＝y(tǒng)1y2…yl′2，P′3＝z1z2…zl′3.

圖1 G的兩個(gè)最小路覆蓋（情況1.1）Fig.1 Two minimum path coverings of G （state 1.1）

圖1的兩個(gè)最小路覆蓋導(dǎo)出了GC的恰有ρ（GC）＝2個(gè)洞的兩個(gè)λ（GC）標(biāo)號(hào)f1和f2，其中：f1（ui）＝i－1，i＝1，2，…，l1；f1（vi）＝l1＋i，i＝1，2，…，l2；f1（wi）＝l1＋l2＋1＋i，i＝1，2，…，l3；f2（xi）＝i－1，i＝1，2，…，l′1；f2（yi）＝l′1＋i，i＝1，2，…，l′2；f2（zi）＝l′1＋l′2＋1＋i，i＝1，2，…，l′3.

由于P1為以?xún)蓚€(gè)葉子點(diǎn)為端點(diǎn)的最長(zhǎng)路，所以有l(wèi)1?｛l′1，l′2，l′3｝，因此由f1導(dǎo)出的島序列不同于由f2導(dǎo)出的島序列，故GC容許兩個(gè)不同的島序列.

為方便，在以下任何已知情況下，均用（P1，P2，P3）和（P′1，P′2，P′3）表示圖G的兩個(gè)最小路覆蓋，用l1，l2，l3和l′1，l′2，l′3表示對(duì)應(yīng)于路覆蓋（P1，P2，P3）和（P′1，P′2，P′3）中每條路的頂點(diǎn)個(gè)數(shù).

情況1.2 兩個(gè)葉子點(diǎn)懸掛在同一個(gè)圈的同一點(diǎn)上.

圖2給出了G的兩個(gè)最小路覆蓋（P1，P2，P3）和（P′1，P′2，P′3）.

圖2 G的兩個(gè)最小路覆蓋（情況1.2）Fig.2 Two minimum path coverings of G （state 1.2）

圖2的兩個(gè)最小路覆蓋導(dǎo)出了GC的恰有ρ（GC）＝2個(gè)洞的兩個(gè)λ（GC）標(biāo)號(hào)f1和f2（標(biāo)號(hào)規(guī)則同情況1.1）.

由于G中每個(gè)圈中的頂點(diǎn)個(gè)數(shù)比每個(gè)藤中的頂點(diǎn)個(gè)數(shù)至少多2，故有l(wèi)′2＞l1.由圖2可得l2＜l′2＞l1＞l′1，并且l3＝l′3.

若l1＝l′3，則l1＝l3，l′2＞l1＝l′3.那么在｛l1，l2，l3｝中有l(wèi)1＝l3，而在｛l′1，l′2，l′3｝中l(wèi)′1≠l′3，l′1≠l′2，l′2≠l′3.

若l1≠l′3，由l′1＜l1＜l′2顯然有l(wèi)1?｛l′1，l′2，l′3｝.

綜上可知，由f1導(dǎo)出的島序列不同于由f2導(dǎo)出的島序列，從而GC容許兩個(gè)不同的島序列.

情況1.3 兩個(gè)葉子點(diǎn)懸掛在同一個(gè)圈的不同點(diǎn)上.

圖3給出了G的兩個(gè)最小路覆蓋（P1，P2，P3）和（P′1，P′2，P′3），其中P1為以?xún)蓚€(gè)葉子點(diǎn)為端點(diǎn)的最長(zhǎng)路，P′1為以?xún)蓚€(gè)葉子點(diǎn)為端點(diǎn)的路，且P1≠P′1.

圖3 G的兩個(gè)最小路覆蓋（情況1.3）Fig.3 Two minimum path coverings of G （state 1.3）

圖3的兩個(gè)最小路覆蓋導(dǎo)出了GC的恰有ρ（GC）＝2個(gè)洞的兩個(gè)λ（GC）標(biāo)號(hào)f1和f2（標(biāo)號(hào)規(guī)則同情況1.1）.

由圖3有l(wèi)1＞l′1，l3＝l′3，所以l1＋l2＝l′1＋l′2，l2＜l′2＜l1（P1為以?xún)蓚€(gè)葉子點(diǎn)為端點(diǎn)的最長(zhǎng)路）.

若l′2＝l3，則l′2＝l′3，l1＞l′2＝l3＞l2，因此有l(wèi)1＞l3＞l2.所以｛l1，l2，l3｝中元素互不相同，而在｛l′1，l′2，l′3｝中有l(wèi)′2＝l′3.

若l′2≠l3，由l2＜l′2＜l1知l′2?｛l1，l2，l3｝.

綜上可知，由f1導(dǎo)出的島序列不同于由f2導(dǎo)出的島序列，從而GC容許兩個(gè)不同的島序列.

情況2 兩個(gè)圈至少有一個(gè)公共點(diǎn)或一條公共邊.

類(lèi)似情況1可給出證明，可參考附圖.

因此p＝2時(shí)，GC容許兩個(gè)不同的島序列.

假設(shè)p＞2，對(duì)于每個(gè)有k（2≤k＜p）個(gè)葉子點(diǎn)的雙圈2－稀疏連通圖G，GC容許至少兩個(gè)不同的島序列.

考慮任意一個(gè)有p（＞2）個(gè)葉子點(diǎn)的雙圈2－稀疏連通圖G，選擇G的一個(gè)藤S，則G－S為有p－1≥2個(gè)葉子點(diǎn)的雙圈2－稀疏連通圖，根據(jù)歸納假設(shè)，H＝（G－S）C容許兩個(gè)不同的島序列.設(shè)g1和g2為H的有ρ（H）個(gè)洞且導(dǎo)出兩個(gè)不同島序列的λ（H）標(biāo)號(hào)，將這兩個(gè)標(biāo)號(hào)延拓到S＝v1v2…vs，給vi（i＝1，2，…，s）分配標(biāo)號(hào)λ（H）＋i＋1，則這兩個(gè)新的標(biāo)號(hào)即為GC的有ρ（H）＋1個(gè)洞的（λ（H）＋s＋1） 標(biāo)號(hào).由引理6有

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

定理2 設(shè)G是有p（p≥2）個(gè)葉子點(diǎn)的雙圈2－稀疏連通圖，且G中至少有一個(gè)圈中的頂點(diǎn)個(gè)數(shù)多于3，則GC是連通的.

當(dāng)u和z在GC中相鄰時(shí)，結(jié)論顯然成立.

設(shè)u和z在GC中不相鄰.由于v1，v2為G中的葉子點(diǎn)，所以u(píng)和z中至少有一個(gè)在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)在GC中與vi（i＝1，2）相鄰，而另一個(gè)在G中與vi（i＝1，2）相鄰.不失一般性，假設(shè)u在GC中與vi（i＝1，2）相鄰，z在G中與vi（i＝1，2）相鄰，因?yàn)関1、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中相鄰，所以u(píng)v1wz即為GC中連通u和z的路.

綜上可得GC是連通的.

［1］ HALE W K.Frequency assignment［J］.Theory and Applications，1980，68：1497－1514.

［2］ GEORGES J P，MAURO D W.On the structure of graphs with non－surjectiveL（2，1）－labelings［J］.SIAM J Disc Math，2005，19：208－223.

［3］ ADAMS S S，TRAZKOVICH A，TROXELL D S，et al.On the island sequences with a condition at distance two［J］.Disc Appl Math，2010，158：1－7.

［4］ 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－111.

附圖

Island sequences ofL（2，1）－labeling of some bicyclic graphs

LUOJin－mei，ZUOLian－cui
（College of Mathematical Science，Tianjin Normal University，Tianjin 300387，China）

It is provided that a class of connected bicyclic graphs with the hole indexρ（G）≥1possessing two different ordered sequences of island cardinalities.

island sequences；light vertex；heavy vertex；2－sparse graphs；hole index；path coveringnumber

O157.5

A

1671－1114（2012）01－0013－04

2011－05－16

天津師范大學(xué)引進(jìn)人才科研啟動(dòng)基金資助項(xiàng)目（5RL066）

雒金梅（1986—），女，碩士研究生.

左連翠（1964—），女，教授，主要從事圖論及其應(yīng)用方面的研究.

（責(zé)任編校 馬新光）